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;
}
```

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!

ReplyDeleteThank you! It's really appreciated!

DeleteGood 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.

ReplyDeleteBest

Peter

qubit101@gmail.com

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

DeleteTo 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?)

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

DeleteI 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):

ReplyDelete// 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

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