Input: A permutation given as an array
Output: A number describing permutation rank
Problem: We are given a permutation and we need to find it’s rank: the position in the permutation sequence where it appears.
Example: 123, rank = 1, 132, rank = 2, 213, rank = 3, etc.
This is a very interesting problem, that leads to another one: recreating permutation on the base of rank number. But this one will be described later. This problem was met during algorithm challenge on Sphere Online Judge.
Obviously, one of the solution would be to generate all the permutations and check the position of the given one. But of course this solution is not satisfactory as the complexity would be O(n!). We need to find a more clever idea.
There is a nice scientific article, if you want to understand the problem deeply. But here we will just keep it basic. Anyway here is the link to Science Direct article. Also Skiena describes a solution for this problem in his “The Algorithm Design Manual”, but for me it’s a little bit fuzzy and it took me a while to get what he means.
Basically the solution I suggest is the one from Skiena’s book, but I would like to explain it in a way that is easier to get, I hope. To make the description easier, let’s suppose the permutation is given as an array, i. e p = [3, 2, 1], describes a permutation of [1,2,3].
In Skiena’s book we are give an interesting recursive relation that looks like following:
How should we interpret it? So we are given a permutation p, it’s rank is counted as a the value of the position number one minus 1, multiplied by the factorial of the size of permutation minus one. So far, so easy and nothing really difficult. But now, is the tricky part. What is exactly the recursive call parameter? It’s a “sub permutation” of p, without the first element and updated values according to a given order.
What do we understand by ordering? It’s the way we set up the order of given set of values. In example ordering of elements [1,2,3,4] is [1,2,3,4], but when we remove element 2 we got [1,3,4] and it’s ordering is [1,2,3] – it means in which place a given number appears in comparison to other elements from the set.
Let’s take an example. Let’s say we have a permutation p = [2, 1, 3] and we are trying to find it’s rank. So the recursive calls look like this:
Let’s stop for a while. How come, in the recursive call we get [1,2], as we already processed 2? Consider it, as after processing 2, it is removed from the ordering. So without 2, the value 3 is now the second element, but value 1 still remains 1. Keep in mind this is related strictly to the ordering you choose. So after this update, [1,3], becomes [1,2]. We process recursively and we get:
As you can see now we updated  to . Finally we got:
You may try with some other permutations to see how it works. Or proceed to the article of unranking permutation.