permute i and T[i]

Question

Assuming that I have an array of int T, I am looking for an in-place algorithm that permute i and T[i]

I have : [3 2 0 1] (a)

I want : [2 3 1 0] (b)

eg. in (b) T[0] = 2 because, in (a) T[2] was equal to 0.

I was expecting to find a simple O(n) time, O(1) space algorithm, but I can't find it. Any ideas ?

Note :

• There is one sigle array (a) is before (b) is after.

• Values in the array belong to [0, N[, no duplicate.

Answer 1

To get the inversion of the permutation, you just have to walk the cycles of the permutation

int i, j, next, prev;
for(int i=0; i<N; i++) {
  if(T[i]>=N) continue;
  j=T[i];
  prev=i;
  while(j < N) {
    next=T[j];
    T[j]=prev+N;
    prev=j;
    j=next;
  }
}
for(int i=0; i<N; i++)
  T[i]-=N;

I use numbers greater than N to mark this is part of a cycle that was already processed.

Answer 2

You can go for lexicographic ordering for getting all the possible permutations. Follow the link below for a list of permutation algorithms

Permutations