Cyclic Permutation

This is an array/list trick that saves about O(n) in space complexity by taking advantage of a given array with integers representing indices.

For this example problem, suppose that we want to apply some permutation P to an array A.
P and A will be both arrays with the same size, but different content.

The two arrays as inputs:

• A or original array (one that contains characters that you want to permute)
• P or permutations (one that contains integers that represent how A should be ordered)

For example, for the following input:

A = ['a', 'b', 'c', 'd']  
P = [1, 3, 0, 2]  

The output then should be

>>> 
['c', 'a', 'd', 'b']

The easy solution

The easy solution to this problem is to have an additional list as a buffer.

def permutation(A, P):  
    buffer = [0] * len(P)  # this costs O(n) extra space
    for i in range(len(P)):
        buffer[P[i]] = A[i]
    A[:] = buffer  # this is the same thing as a shallow copy for lists

This algorithm is about O(n) in space complexity and O(n) in time complexity.
This is a nice starting ground for optimizations.

The trickier follow-up solution

There is a way to reduce the space complexity here from O(n) to O(1).
As mentioned above, it involves exploiting the P array.

But first, the key observation here is to realize that without an additional buffer or temporary storage, it's difficult to determine which values to swap.

Consider the following scenario:

A = ['a', 'b', 'c', 'd']  
P = [1, 3, 2, 0]  

Suppose that we iterate through A or P, and i is at index 0.
We see that P[0] is 1, which tells us that A[0] or 'a' needs to be in position 1.

We can try swapping the values at A[0] and A[1] with the following code:

A[i], A[p[i]] = A[p[i]], A[i]  

Note that this is basically equivalent to:

temp = A[i]  
A[i] = A[p[i]]  
A[p[i]] = temp  

So now, our array A looks like this:

>>> A
['b', 'a', 'c', 'd']

All good so far, or so it seems. a is now in position 1, which is, according to P, accurate.
Note that b is not in the right position, but we'll assume at this point that b's position will be resolved as we fully iterate through the list.

Now we increment i so i is now 1.

We'll do the same swapping logic as before. In this case:

A[1], A[p[1]] = A[p[1], A[1]]  # this is equivalent to A[1], A[3] = A[3], A[1]  

Then, a problem arises. A[1], which points to 'a', is in the correct position, but we are swapping this value again, effectively setting A[1] to some other value.

A is now ['b', 'd', 'c', 'a'], which doesn't look accurate at all with the exception of the placement of 'c', only because c was always in the correct position 2 and was never touched. We've basically backtracked.

Cyclic property

If the list P is a list that contains indices of A, and A is the same size as P, then it is safe to say that all indices in P is valid (i.e., we shouldn't have an IndexError if we try to use any value in P as an index to A)

One interesting thing about these indices is that it represents a cycle.

Using the original example from above:

A = ['a', 'b', 'c', 'd']  
P = [1, 3, 2, 0]  

Then we first look at A[0] and P[0]. P[0] points at index 1.
Then we look at P[P[0]], or P[1], and we see that this points to index 3.
Then we look at P[P[P[0]]], or P[3], and we see that this points to index 0.
And now, we come to the realization that index 0 is precisely where we started. This is a graph representation of a cycle.

By making use of this cyclic property, we can swap two values one at a time from the start and keep swapping until we see the start again. This will ensure that the values that are swapped are in the correct locations.

Are these two values already swapped?

Although we can keep going following this cyclic chain, we need a way to tell the compiler how to stop. Naturally, a flag that states that the two values X and Y are swapped is ideal. Therefore, we could have a boolean array for this, but this violates the goal of reducing our space complexity from O(n) -> O(1).

What if we subtract the index representing a "swapped" pair of values with the size of A?

Since A is the maximum size of the array, and indices of A is from 0 ... len(A)-1, this guarantees that the index will always be negative as a result of the subtraction. Negative values can be the flag that states that the two values X and Y are swapped. On top of that, this process is easily reversible and we can bring back P's negative numbers back to positive (and valid as indices) ones by adding each of the negative numbers with len(A).

Putting it in code

def permutations(A, P):  
    for i in range(0, len(A)):
        next = i

        while P[next] >= 0:
            # For debugging
            print('i = {} \ta = [{}]\tp = [{}]'.format(str(i),
                                                       " ".join(A),
                                                       " ".join([str(x) for x in P])))
            A[i], A[P[next]] = A[P[next]], A[i]
            temp = P[next]
            P[next] -= len(A)  # This guarantees that we'll have a negative number, since any elem in P < len(A) or len(P)
            next = temp
    P[:] = [n + len(P) for n in P]  # All values of P should be negative now. Restore P to it's former glory.