permute i and T[i]

Question

Hi,

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

Answer 3

It seems that you're looking for the inverse in the permutation group of an array. Your example array is {0→3, 1→2, 2→0, 3→1}, and you want {3→0, 2→1, 0→2, 1→3}. Rearranged, that's {0→2, 1→3, 2→1, 3→0}, or [2 3 1 0]. So, to find the inverse, you just need to iterate through the original array and reverse the mapping of indices. This should work (you can use any array if you know the length):

int t[] = { 3, 2, 0, 1};
int tinv[4];
for (int i = 0; i < 4; i++)
    tinv[t[i]] = i;

So long as t (with length n) is a permutation of [0 .. n-1], tinv shouldn't be undefined for any values. jpalecek's solution is somewhat more complicated, so I'm not sure if this one is comprehensive enough for you.

Answer 4

This is my attempt to solve this problem in-place without extra memory. It is a O(n) algorithm.

The algorithm by jpalecek is quite intelligent but not intuitive to read, at least not for me. I've tried it out and it works but I haven't had the time to understand why and comments would be great.

The algorithm by Gracenotes is great as long as the array isn't too big. If the data is large, one may have to create the array dynamically.

The basic idea in my algorithm is to update the array by following the chain of index and value pairs. For example index 0 maps to value 3. By using value 3 as the index you will find the next pair which is index 3 in the array and value 1. Essentially I save the next index and value pair and update the previous index and pair value until I am done the chain.

If you can make it more efficient, elegant or better overall, I would be interested.

I've compiled and tested the code below but haven't used any other test input. I've left in debug output for those who wish to try it out and better understand how it works.

// Array print routine.
void printArray (const char * str_p,int a[], int n)
{
   printf ("%s\n", str_p);
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", i);
   }
   printf ("\n");
   for (int i = 0; i < n; i++)
   {
      printf ("%i ", a[i]);
   }
   printf ("\n\n");
}

// The main code.
void PermuteTheDamnArray()
{
   printArray ("Initial Array", a,n);

   int i = 0;     // Simply a counter.
   int p_ix = 0;  // Previous Index.
   int p_val = a[0]; // Previous Value.
   int n_ix = a[0];  // Next index.
   int n_val = a[n_ix]; // Next Value.
   for (i = 0; i < n; i++)
   {
      // Replace. 
      printf ("Swapping orig (%i,%i) with (%i,%i)\n", n_ix, n_val,p_val, p_ix);
      a[p_val] = p_ix;

      printArray ("Array after swap", a,n);

      // The next index and value pair becomes the new previous index and value pair.
      p_ix = n_ix;
      p_val = n_val;
      printf ("The previous pair is now: (%i,%i)\n", p_ix, p_val);

      // Get the next index and value pair.
      n_ix = n_val;
      n_val = a[n_val];
      printf ("The next pair is now: (%i,%i)\n", n_ix, n_val);

   }

   printArray ("Final Array", a,n);
}



Output:

Swapping orig (3,1) with (3,0)
Array after swap
0 1 2 3 
3 2 0 0 

The previous pair is now: (3,1)
The next pair is now: (1,2)
Swapping orig (1,2) with (1,3)
Array after swap
0 1 2 3 
3 3 0 0 

The previous pair is now: (1,2)
The next pair is now: (2,0)
Swapping orig (2,0) with (2,1)
Array after swap
0 1 2 3 
3 3 1 0 

The previous pair is now: (2,0)
The next pair is now: (0,3)
Swapping orig (0,3) with (0,2)
Array after swap
0 1 2 3 
2 3 1 0 

The previous pair is now: (0,3)
The next pair is now: (3,0)
Final Array
0 1 2 3 
2 3 1 0