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

Step 1.

Unrank(3, 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]

Step 2.

Unrank(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] = [1]

Step 3.

Unrank(0, 1):
Ordering [1] = [1]
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).**

Best Regards

Joe Kidd

### Like this:

Like Loading...