Re: Dijkstra - Algorithms Discussion Boards

Efficiently finding position in sorted list

Robert Ellis26-Mar-23 13:52

26-Mar-23 13:52

Say we have a set of positive integer numbers and the size of the set is always Q

For each position in the set we can define a minimum value and maximum value, both inclusive, for the value that could appear at that position in the set.

We can then deterministically sort a list of all of the distinct permutations of Q. To do so, We will sort first by the position 1 value, then (where the position 1 value is the same across multiple permutations) by the position 2 value and so on and so forth through to position Q being the least significant for the sort.

Given a single valid permutation of this type, is there a mathematically efficient way of determining its position in the sorted list, that is, without ever creating or iterating the list?
Conceptually reversing the above, given a position in the sorted list, is there a mathematically efficient way of determining the corresponding permutation, without ever creating or iterating the list?

Re: Efficiently finding position in sorted list

Mircea Neacsu26-Mar-23 14:42

Mircea Neacsu

26-Mar-23 14:42

Hmm, if I understand correctly, we have a list of Q positions where each one has a specific range say:
1 - [m_1, u_1]
2 - [m_2, u_2]
...
q - [m_q, u_q]
where m_1 to m_q are the minimum values and u_1 to u_q are the maximum (upper) values. A valid arrangement (I wouldn't call it a permutation) V = [v_1, v_2, ... v_q] can be "normalized" by subtracting the vector M = [m_1, m_2, ..., m_q] of minimum values. Let N = V-M be the normalized vector and R = U-M be the vector of ranges. Note that n_i < r_i.

I will change your problem to set the least significant position to be position 1 just for ease of notation. Then position of V in the list of arrangements is given by the sum:
S = n_1 + n_2*r_1+n3*r_1*r_2 + ...n_q * r_1*r_2*...*r_q-1

This is a bit like expressing a number in a "variable" base. The number of "digits" available at position i is r_i.

Mircea

Dijkstra

Calin Negru13-Dec-22 7:46

Calin Negru

13-Dec-22 7:46

Is the problem with dijkstra the fact that it computes not only the shortest path towards the destination but also the shortest path from the starting tile to any other tile in the search area ?