How can I calculate n-th permutation (or tell the lexicographic order of a given permutation)?

Question

This question has two parts, though since I'm trying to compe up with a Prolog implementation, solving one will probably immediately lead to a solution of the other one.

1. Given a permutation of a list of integers {1,2,...,N}, how can I tell what is the index of that permutation in lexicographic ordering?
2. Given a number k, how can I calculate k-th permutation of numbers {1,2...,N}?

I'm looking for an algorithm that can do this reasonably better than just iterating a next permutation function k times. Afaik it should be possible to directly compute both of these.

What I came up with so far is that by looking at numbers from the left, I can tell how many permutations were before each number at a particular index, and then somehow combine those, but I'm not really sure if this leads to a correct solution.

Answer 1

Think how many permutations start with the number 1, how many start with the number 2, and so on. Let's say n = 5, then 24 permutations start with 1, 24 start with 2, and so on. If you are looking for permutation say k = 53, there are 48 permutations starting with 1 or 2, so #53 is the fifth of the permutations starting with 3.

Of the permutations starting with 3, 6 each start with 31, 32, 34 or 35. So you are looking for the fifth permutation starting with (3, 1). There are two permutations each starting with 312, 314 and 315. So you are looking for the first of the two permutations starting with 315. Which is 31524.

Should be easy enough to turn this into code.

Answer 2

You can also have a look at the factorial number system, especially the part regarding permutations. For a given number k, you are first supposed to find its factorial representation, which then easily gives the required permutation (actually, (k+1)-st permutation).

An example for k=5 and numbers {1,2,3}:

5 = 2*2! + 1*1! + 0*0! = (210)_!

so the factorial representation of 5 is 210. Let's now map that representation into the permutation. We start with the ordered list (1,2,3). The leftmost digit in our factorial representation is 2, so we are looking for the element in the list at the index 2, which is 3 (list is zero-indexed). Now we are left with the list (1,2) and continue the procedure. The leftmost digit in our factorial representation, after removing 2, is 1, so we get the element at the index 1, which is 2. Finally, we are left with 1, so the (k+1)-st (6th) permutation of {1,2,3} is {3,2,1}.

Even though it takes some time to understand it, it is quite efficient algorithm and simple to program. The reverse mapping is similar.

Answer 3

I'll just give the outline of a solution for each:

Given a permutation of a list of integers {1,2,...,N}, how can I tell what is the index of that permutation in lexicographic ordering?

To do this, ask yourself how many permutations start with 1? There are (N - 1)!. Now, let's do an example:

3 1 2

How many permutations of 1 2 3 start with 1 or 2? 2*2!. This one has to be after those, so its index is at least 2*2! = 4. Now check the next element. How many permutations of 1 2 start with 0? None. You're done, the index is 4. You can add 1 if you want to use 1-based indexing.

Given a number k, how can I calculate k-th permutation of numbers {1,2...,N}?

Given 4, how can we get 3 1 2? We have to find each element.

What can we have on the first position? If we have 1, the maximum index can be 2! - 1 = 1 (I'm using zero-based indexing). If we have 2, the maximum can be 2*2! - 1 = 3. If we have 3, the maximum can be 5. So we must have 3:

3

Now, we have reduced the problem to finding the 4 - 2*2! = 0-th permutation of 1 2, which is 1 2 (you can reason about it recursively as above).