Thursday 10 July 2014

Mapping between permutations and natural numbers

This algorithm is composed of two functions, one mapping a natural number between 0 and n!-1 to a unique permutation, and the other its inverse. Both are in O(n), you can find the code here: http://pastebin.com/0EU5v3dd.

See here (Joren's answer) for a good explanation on Lehmer's code which my algorithm is based on. The algorithm he presents is in O(n^2) because it needs to find the nth element in an array filled with holes. This means it needs to iterate over the elements in the list until it finds the nth non-empty element.

My idea was to keep a list without holes, which means finding the nth remaining element in one operation. To do this, every time you remove an element from the array, you swap the last element of the array in the position of the one you just removed. We can thus keep a list without holes doing only a few operations each time we remove an element: elems[ind]=elems[n-i-1].

You can work out the inverse function yourself it's pretty fun.

 public static int[] perm(int n, int k)  
 {  
      int i, ind, m=k;  
      int[] permuted = new int[n];  
      int[] elems = new int[n];  
      for(i=0;i<n;i++) elems[i]=i;  
      for(i=0;i<n;i++)  
      {  
           ind=m%(n-i);  
           m=m/(n-i);  
           permuted[i]=elems[ind];  
           elems[ind]=elems[n-i-1];  
      }  
      return permuted;  
 }  
 public static int inv(int[] perm)  
 {  
      int i, k=0, m=1;  
      int n=perm.length;  
      int[] pos = new int[n];  
      int[] elems = new int[n];  
      for(i=0;i<n;i++) {pos[i]=i; elems[i]=i;}  
      for(i=0;i<n-1;i++)  
      {  
           k+=m*pos[perm[i]];  
           m=m*(n-i);  
           pos[elems[n-i-1]]=pos[perm[i]];  
           elems[pos[perm[i]]]=elems[n-i-1];  
      }  
      return k;  
 }  

8 comments:

  1. Just wanted to thank you for your algorithm. I was looking for a way of storing and applying any possible permutation of N elements in my C++ and JavaScript code, and came across your answer in the Stack Overflow site. It works beautifully. Great work!

    ReplyDelete
  2. Good job Antoine! I was just searching an O(n) solution. Have you published your algorithm? I need reference it on my work, please let me know.
    Best
    Peter
    qubit101@gmail.com

    ReplyDelete
    Replies
    1. Thank you! It's not published, so I guess you could just link to this post.

      Delete
  3. To clarify, this does not actually use lehmer codes anymore, right? It's just a bijection? (And this the sum of digits in our code is not the number of inversions?)

    ReplyDelete
    Replies
    1. Indeed, the resulting order has nothing to do with Lehmer's code, my algorithm is only a tweak on the algorithm using it.

      Delete
  4. I needed the inverse permutation, so that I could restore permuted vectors to order when k is unknown. Here is the code (since you posted in Java without stating the programming language, I will do the same thing):

    // Compute the inverse of a permutation
    function GetInvPerm($Perm)
    {
    $n=count($Perm);
    $InvPerm=[];
    for ($i=0; $i<$n; ++$i)
    $InvPerm[$Perm[$i]]=$i;
    return $InvPerm;
    } // GetInvPerm

    David Spector
    Springtime Software

    ReplyDelete
  5. Thank you soo much for the code. It helped me figure out the formulas finally and also make a converter from the permutation to the factoradic system in javascript!

    ReplyDelete