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

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.