Input: A number M, describing a rank of permutation of N elements
Output: Permutation with a given rank
Problem: We are given a rank and we need to find the proper permutation
Example: rank=1 p=123, rank = 2 p=132, rank = 3, p=213, etc.
In this article we have discussed how to find a rank of a permutation. Now let’s try to do the opposite thing: knowing the rank, find the proper permutation.
We will use the idea described in Skiena’s book, “The Algorithm Design Manual” (if you don’t have it yet, go and buy, as it’s a nice source of algorithmic problems and mr. Skiena seems to be a clever guy).
So we have a function Unrank(M, N), that according to the definition of the problem, tries to find what is the permutation at M position, in a permutation of N elements, having some order of generation.
Let me remind the Rank function from the article, that is given in the following way:
How can we revert the permutation from the given rank number? The part gives us an information how many permutations of size |p| appears, before we got the value at at the first position. Then we proceed for the next number by a recursive call. In this case we have to find such a maximum number X for , that there will be at max M permutations in front of him. So the following condition has to to be met:
Getting this number, we are updating ordering, as it was previously described in the rank algorithm and then we proceed for a problem with smaller size.
Let’s take an example to see if we correctly understand the problem. Let’s say we are looking for M = 3, N = 3.
Ordering [1,2,3] => [1,2,3]
X = 3, then (3 - 1) * (3 - 1)! = 4 > 3, condition not met
X = 2, then (2 - 1) * (3 - 1)! = 2 <= 3, condition met, so p1 = 2
Update the ordering removing 2, we [1,2,3] => [1,x, 3 - 1] = [1,2]
Ordering [1,3] => [1,2]
X = 2, then (2 - 1) * (2 - 1)! = 1 <= 2, condition ment, so p2 = 3
Update the ordering removing 2, we [1,2] => [1,x] = 
Ordering  = 
As we are looking for 0 element for 1 element ordering it will be
exactly this element, so p3 = 1
So the given permutation is p = [2, 3, 1] and using rank algorithm we can really check that this answer is correct. The M parameter also changes with the recursion. If we figured out that the element with rank Y should be used, then in the next step M = max(M – Y, 0).