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[0]` and `arr[1]`; The second one rotates between `arr[2]`, `arr[3]`, and `arr[4]`. 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.