Permuting an Array

DYX

This document introduces the well-known general algorithm to permute an array with O(n) time and O(1) space. Then a simpler algorithm is presented. It only works for the integer type. But it’s easier to implement and has the same time and space complexity.

Introduction to the Problem

With a given array arr and a permutation perm, rearrange the order of arr as perm indicates. More specifically, place the arr[perm[i]] into arr[i].

For example, with arr={3, 5, 4, 8, 2} and perm={1, 0, 4, 3, 2}, the result is {5, 3, 2, 8, 4}.

It’s easy to solve the problem in O(n) time, thus the key is to solve it in O(1) extra space.

The General Algorithm

There is a well-known solution to this problem. The idea is that any permutation can be decomposed into several rotations. A rotation is a special permutation which moves elements cyclically. It moves the second element to the position of the first, the third to the second, and so on; At last it moves the original first element to the last position. For example, {1, 0, 4, 3, 2} is decomposed into two rotations. The first one rotates between arr and arr; The second one rotates between arr, arr, and arr. This algorithm iterates every element of arr and finds the rotation containing the element and rotates all relevant elements. After rotation, it denotes those elements as having been placed in desired positions by setting perm[j] to j.

int *permute(int *arr, int *perm, unsigned n)
{
int i, j, next, swap;

for (i = 0; i < n; ++i) {
swap = arr[i], j = i;
while (perm[j] != i) {
next = perm[j];
arr[j] = arr[next], perm[j] = j;
j = next;
}
arr[j] = swap, perm[j] = j;
}
return arr;
}

A Simpler Algorithm for Integer Type

The above algorithm is hard to implement and analyze, easy to make bugs. In many cases the type of elements is int. A simpler algorithm could be used in such cases. The basic idea is reusing perm to save original values of arr. Once the new value of arr[i] is set, save the old value in perm[i]. perm is thus split into two parts. The first part stores old values of arr and the second part stores the real permutation.

int *permute_int(int *arr, int *perm, unsigned n)
{
int i, swap;

for (i = 0; i < n; ++i) {
swap = arr[i];
arr[i] = perm[i] < i ? perm[perm[i]] : arr[perm[i]];
perm[i] = swap;
}
return arr;
}

permute_int also takes O(n) time and O(1) extra space and is easier to implement.