Adjacent values

Question

I need to create an algorithm that calculates the minimum distance value between the indexes of a matrix that contains adjacent values. But what are adjacent values someone could give me examples?

For example, in matrix A such that:

  

  A [0] = 0
  A [1] = 3
  A [2] = 3
  A [3] = 7
  A [4] = 5
  A [5] = 3
  A [6] = 11
  A [7] = 1

The following pairs of values have adjacent indices:

  (0, 7), (1, 2), (1, 4),

  (1, 5), (1, 7), (2, 4),

  (2, 5), (2, 7), (3, 4),

  (3, 6), (4, 5), (5, 7).

Indices 4 and 5 have adjacent values because there is no value in array A

which is strictly between A [4] = 5 and A [5] = 3; the only such value could be number 4,

and that is not present in the matrix.

Answer 1

Adjacent values can have many different meanings, and depend mainly on the problem statement and the area to which it applies.

Two step-by-step examples, to show different rules for the concept adjacent values.

Example 1

Extracted from the question in the OS in English:

Trying to Sort and find the Nearest pair of Adjacent values in an array in C#

In this case, the rule is:

...
A non-empty zero-index A array contains integers N.
An index pair (P, Q) where 0 P < Q < N is said to be adjacent, if no value "is strictly" between A[P] and A[Q].
...

Here, the rule for creating tuples (P, Q) indicates that there can be no values between two elements, therefore:

Valor   |  0 |  3 |  3 |  7 |  5 |  3 | 11 |  1 |  
--------+----+----+----+----+----+----+----+----+  
Índice  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |  

Tuples (P, Q) index (explanation follows the rating valor[índice] or valor):

(0, 1)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 2)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 3)  => não, porque tem o valores 1[7] e 5[4] entre 0 e 7
(0, 4)  => não, porque tem o valor 1[7] e 3[1] entre 0 e 5
(0, 5)  => não, porque tem o valor 1[7] entre 0 e 3
(0, 6)  => não, porque tem o valores 1[7], 3[1], 5[4] e 7[3] entre 0 e 11
(0, 7)  => SIM, porque não há valor entre 0 e 1 (adjacentes)

(1, 2)  => SIM, porque não há valor entre 3 e 3 (adjacentes)
(1, 3)  => não, porque tem o valor 5[4] entre 3 e 7
(1, 4)  => SIM, porque não há valor entre 3 e 5 (adjacentes)
(1, 5)  => SIM, porque não há valor entre 3 e 3 (adjacentes)
(1, 6)  => não, porque tem o valores 5[4] e 7[3] entre 3 e 11
(1, 7)  => SIM, porque não há valor entre 3 e 1 (adjacentes)

(2, 3)  => não, porque tem o valor 5[4] entre 3 e 7
(2, 4)  => SIM, porque não há valor entre 3 e 5 (adjacentes)
.....
.....
.....

And following these steps, you get the set of tuples:

(0, 7), (1, 2), (1, 4),
(1, 5), (1, 7), (2, 4),
(2, 5), (2, 7), (3, 4),
(3, 6), (4, 5), (5, 7)

---

Example 2

Similar to the question asked by you at:

Algorithm of adjacent numbers with complexity O (N * log (N))

I am guessing that the origin is similar to the following challenge on the site Codility:

Shortest Adjacency Sequency

(I didn’t copy the text here because of copyright, but just click on the link and button View on the website)

The shortest path of the first element must be found (1) to the last element (2), following the rules described in link above.

Example vector:

Valor   |  1 | 10 |  6 |  5 | 10 |  7 |  5 |  2 |
--------+----+----+----+----+----+----+----+----+
Índice  |  0 |  1 |  2 |  3 |  4 |  5 |  6 |  7 |

Some possible paths (explanation follows notation valor[índice] or value):

[1, 10, 6, 5, 10, 7, 5, 2]

Explanation: is the original vector itself.

[1, 10, 6, 5, 10, 7, => 5, 10, 7, 5, 2]

Explanation: Traverse the vector to the value 5[6], back to value 5[3] (adjacent) and continues to the end.

[1, 10, 6, 5, => 10, 6, 5, 10, 7, 5, 2]

Explanation: Traverse the vector to the value 10[4], back to value 10[1] (adjacent) and continues to the end.

[1, => 10, 7, 5, 2];

Explanation: Traverse the vector to the value 10[1], jumps to the value 10[4] (adjacent) and continues to the end.

[1, => 10, => 5, 2]

Explanation: Traverse the vector to the value 10[1], jumps to the value 10[4] (adjacent), back to value 5[3] (previous), skip to the value 5[6] (adjacent) and continues to the end.

In this example, according to the problem, the (shortest) solution is the [1, 10, 5, 2].

---

Therefore, the term valores adjacentes depends on the rule specified in the problem and also the area where the term is used (as per the comments).

Below is an implementation (in Python) of example 2:

Codility Iota 2011 Coding Challenge - Shortestadjseq