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.