Algorithm for applying permutation in the space of read-only memory

Question

I saw that this question is a book for programming interviews, here I simplify the question.

Suppose you have an array A length n , and you have an array of permutations P length n . Your method will return an array in which elements of A appear in order with the indices specified in P

A quick example: your method takes A = [a, b, c, d, e] and P = [4, 3, 2, 0, 1] . then it will return [e, d, c, a, b] . You are allowed to use only constant space (i.e. you cannot allocate another array that occupies the space O(n) ).

Ideas?

Answer 1

There is a trivial O (n ^ 2) algorithm, but you can do it in O (n). For example:.

A = [a, b, c, d, e]

P = [4, 3, 2, 0, 1]

We can exchange each element in A with the necessary element required by P , after each swap in the right position there will be another element and do it in a circular manner for each of the positions (swap elements marked with ^ s):

 [a, b, c, d, e] <- P[0] = 4 != 0 (where a initially was), swap 0 (where a is) with 4 ^ ^ [e, b, c, d, a] <- P[4] = 1 != 0 (where a initially was), swap 4 (where a is) with 1 ^ ^ [e, a, c, d, b] <- P[1] = 3 != 0 (where a initially was), swap 1 (where a is) with 3 ^ ^ [e, d, c, a, b] <- P[3] = 0 == 0 (where a initially was), finish step 

After one circle, we will find the next element in the array that will not remain in the correct position, and do it again. Thus, at the end you will get the desired result, and since each position touches a constant time (no more than one operation (swap) is performed for each position), this is O (n) time.

You can save information about which one is in the right place:

• set the corresponding entry in P to -1, which cannot be restored: after the operations described above, P will become [-1, -1, 2, -1, -1] , which means that only the second one may not be in the correct position, but one more the step will make sure that it is in the correct position and completes the algorithm;

• set the corresponding entry in P to -n - 1 : P becomes [-5, -4, 2, -1, -2] , which can be restored to O (n) trivially.

Answer 2

Another unnecessary answer! This saves an explicit array of permutations of P , which was necessary for my situation, but sacrifices costs. Also, it does not require tracking correctly placed elements. I understand that the previous answer provides an O(N) solution, so I think this is just for fun!

We get the best case complexity O(N) , the worst case O(N^2) and the average case O(NlogN) . For large arrays ( N~10000 or more), the average case is essentially O(N) .

Here is the basic algorithm in Java (I mean pseudo-code * cough cough *)

 int ind=0; float temp=0; for(int i=0; i<(n-1); i++){ // get next index ind = P[i]; while(ind<i) ind = P[ind]; // swap elements in array temp = A[i]; A[i] = A[ind]; A[ind] = temp; } 

Below is an example of the algorithm (similar to the previous answers):

let A = [a, b, c, d, e]

and P = [2, 4, 3, 0, 1]

then expected = [c, e, d, a, b]

 i=0: [a, b, c, d, e] // (ind=P[0]=2)>=0 no while loop, swap A[0]<->A[2] ^ ^ i=1: [c, b, a, d, e] // (ind=P[1]=4)>=1 no while loop, swap A[1]<->A[4] ^ ^ i=2: [c, e, a, d, b] // (ind=P[2]=3)>=2 no while loop, swap A[2]<->A[3] ^ ^ i=3a: [c, e, d, a, b] // (ind=P[3]=0)<3 uh-oh! enter while loop... ^ i=3b: [c, e, d, a, b] // loop iteration: ind<-P[0]. now have (ind=2)<3 ? ^ i=3c: [c, e, d, a, b] // loop iteration: ind<-P[2]. now have (ind=3)>=3 ? ^ i=3d: [c, e, d, a, b] // good index found. Swap A[3]<->A[3] ^ done. 

This algorithm can bounce in this while for any indices j<i , no more than i times during the ith iteration. In the worst case (I think!) Each iteration of the outer for loop would lead to additional assignments of i from the while , so we would continue the arithmetic series that would add N^2 complexity factor! Doing this for the N range and averaging the number of “extra” assignments needed by the while (averaged over many permutations for each N , that is), however, strongly suggests that the average case is O(NlogN) .

Thanks!

Answer 3

Just a simple example of adding C / C ++ code to Ziyao Wei's answer. The code is not allowed in the comments, so sorry as a response

 for (int i = 0; i < count; ++i) { // Skip to the next non-processed item if (destinations[i] < 0) continue; int currentPosition = i; // destinations[X] = Y means "an item on position Y should be at position X" // So we should move an item that is now at position X somewhere // else - swap it with item on position Y. Then we have a right // item on position X, but the original X-item now on position Y, // maybe should be occupied by someone else (an item Z). So we // check destinations[Y] = Z and move the X-item further until we got // destinations[?] = X which mean that on position ? should be an item // from position X - which is exactly the X-item we've been kicking // around all this time. Loop closed. // // Each permutation has one or more such loops, they obvisouly // don't intersect, so we may mark each processed position as such // and once the loop is over go further down by an array from // position X searching for a non-marked item to start a new loop. while (destinations[currentPosition] != i) { const int target = destinations[currentPosition]; std::swap(items[currentPosition], items[target]); destinations[currentPosition] = -1 - target; currentPosition = target; } // Mark last current position as swapped before moving on destinations[currentPosition] = -1 - destinations[currentPosition]; } for (int i = 0; i < count; ++i) destinations[i] = -1 - destinations[i]; 

(for C - replace std :: swap with something else)

Answer 4

Thus, you can put the desired element at the beginning of the array, working with the remaining array of size (n-1) in the next iteration step.

The permutation array must be appropriately configured to reflect the decreasing size of the array. Namely, if the element that you placed in the front was found in the "X" position, you need to reduce by one all the indices greater than or equal to X in the permutation table.

In the case of your example:

 array permutation -> adjusted permutation A = {[abcde]} [4 3 2 0 1] A1 = { e [abcd]} [3 2 0 1] -> [3 2 0 1] (decrease all indexes >= 4) A2 = { ed [abc]} [2 0 1] -> [2 0 1] (decrease all indexes >= 3) A3 = { edc [ab]} [0 1] -> [0 1] (decrease all indexes >= 2) A4 = { edca [b]} [1] -> [0] (decrease all indexes >= 0) 

Another example:

 A0 = {[abcde]} [0 2 4 3 1] A1 = { a [bcde]} [2 4 3 1] -> [1 3 2 0] (decrease all indexes >= 0) A2 = { ac [bde]} [3 2 0] -> [2 1 0] (decrease all indexes >= 2) A3 = { ace [bd]} [1 0] -> [1 0] (decrease all indexes >= 2) A4 = { aced [b]} [0] -> [0] (decrease all indexes >= 1) 

The algorithm, although not the fastest, allows you to avoid additional memory allocation, while maintaining tracking of the initial order of elements.

Answer 5

The return value for the example given in the initial question is incorrect.

 A = [abcde] P = [4 3 2 0 1] SHOULD return [decba] not as as indicated in the question ([edcab]) 

Answer 6

Here's a more understandable version that accepts a swapElements function that accepts indices, for example, std::swap(Item[cycle], Item[P[cycle]])$ Essentially, it goes through all the elements and follows the cycles if they don’t have been visited yet. Instead of the second check !visited[P[cycle]] , we can also compare with the first element in the loop, which was made somewhere else above.

  bool visited[n] = {0}; for (int i = 0; i < n; i++) { int cycle = i; while(! visited[cycle] && ! visited[P[cycle]]) { swapElements(cycle,P[cycle]); visited[cycle]=true; cycle = P[cycle]; } } 

Answer 7

@RinRisson has given the only correct answer so far! Each other answer was something that required additional memory - O (n) stack space, or it was assumed that the permutation P was conveniently stored next to O (n) unused but mutable sign bits, or something else.

Here RinRisson the correct answer is written out in C ++. This passes every test that I conducted, including an exhaustive test of every possible permutation of lengths from 0 to 11.

Note that you do not even need a permutation to materialize; we can consider it as a completely black function OldIndex → NewIndex :

 template<class RandomIt, class F> void permute(RandomIt first, RandomIt last, const F& p) { using IndexType = std::decay_t<decltype(p(0))>; IndexType n = last - first; for (IndexType i = 0; i + 1 < n; ++i) { IndexType ind = p(i); while (ind < i) { ind = p(ind); } using std::swap; swap(*(first + i), *(first + ind)); } } 

Or add more STL interface:

 template<class RandomIt, class ForwardIt> void permute(RandomIt first, RandomIt last, ForwardIt pfirst, ForwardIt plast) { assert(std::distance(first, last) == std::distance(pfirst, plast)); permute(first, last, [&](auto i) { return *std::next(pfirst, i); }); } 

Answer 8

I agree with many of the solutions here, but below is a very short piece of code that swaps over the entire permutation cycle:

 def _swap(a, i, j): a[i], a[j] = a[j], a[i] def apply_permutation(a, p): idx = 0 while p[idx] != 0: _swap(a, idx, p[idx]) idx = p[idx] 

So the code snippet below

 a = list(range(4)) p = [1, 3, 2, 0] apply_permutation(a, p) print(a) 

Outputs [2, 4, 3, 1]