Apply Permutation to an Array

 

Venice Beach, LA

The following may seem like an easy question if you know that permutations have cycles...

A permutation can be specified by an array P, where P[i] represents the location of the element at i in the permutation. For example, [2, 1, 0] represents the permutation where elements at the index 0 and 2 are swapped.

Given an array and a permutation, apply the permutation to the array. For example, given the array ["a", "b", "c"] and the permutation [2, 1, 0], return ["c", "b", "a"].

Understanding the Problem

Each element of the permutation array contains target indexes. The index of each of these elements represents the source index of the character array.

For the example in the problem statement 

• we can move 'a' which is at index 0 to position specified the permutation array - 2,
• we move'c' which is at index 2 to position 0.
• 'b' is moved to the same position 1

Solving it

One way of solving this problem in O(N) runtime and O(N) memory is to simply create a new result array and then traverse the source and use the permutation array to populate the results in the result array

Less Memory

It is possible to improve the solution by using O(1) memory

One approach is to move each character from the source location to the target destination while saving the replaced character in a temp variable. We now repeat this process with the replaced char in the temp variable and the next target destination, until we reach the end. But how do we determine when to end ?

Permutations are cyclic and therefore -

• We need a way to know when to stop processing. Setting the target permutation element to -1 will indicate to the code that we have already processed that element
• Permutations can have more than one cycle and therefore marking the processed targets lets us move on to the cycles that haven't been processed
• Lastly, because of the cyclic nature of each permutation it is possible to forgo a temp variable and instead just use the first element in the cycle as a temp variable
  

Cyclic nature of a permutation

In the problem example, 'a' and 'c' are part of the same cycle in the permutation. For larger examples, by continually swapping the elements "forward",  we will end up with the last character in the cycle in the first position. We can therefore use this first position as a temp variable.

And for a slightly more complex permutation, in the diagram below if we were to utilize the first element at index 0 as a temp variable, and use that to swap the character to the target position. We will eventually end up with the last character in the permutation in the temp element location.

Understanding the code

Here is a subsection of the code from -

https://www.geeksforgeeks.org/permute-the-elements-of-an-array-following-given-order/

while (P[next] >= 0)
{
    swap(C, i, P[next]);

    int temp = P[next];
    P[next] = -1;
    next = temp;
}

For each cycle, we use the starting element of the cycle as a temp variable while moving the source char to the target location. 

Another temp variable is also used to store the next target index while negating it to indicate that it was processed.

The following diagrams illustrate 2 iterations of the code when attempting to permutate the following array