Permute Elements of An Array

Given an array A of n elements and a permutation P , where P[i] indicates the location where the current A[i] goes. Apply P to A .

Example

Input: A = [a,b,c,d], P = [3,2,1,0]
Output: [d,c,b,a]

Solution

Idea:

• Every permutation can be represented by a collection of independent permutations, each of which is cyclic.

• In each cycle, alternate elements in A one by one.

• After one location is alternated, deduct len(A) from the location index. Then after this cycle is done, we know which location is already alternated (locations with negative values).

Time complexity: $O(n)$

Space complexity: $O(1)$

def apply_permutation(A, P):
    for i in range(len(A)):
        next = i
        while P[next] >= 0 :
            A[next], A[P[next]] = A[P[next]], A[next]
            next = P[next]
            # make P[next] negative once it is used
            P[next] -= len(A)
    return A