Finding position of specific permutation in alphabetically ordered list of permutations on elements {1,2, ... , k}

Question

I have to create two algorithms (but I think it is more of a combinatorics question).

Let there be list of permutations on elements $\{1,2,...,k\}, k \in N$ and this list is alphabetically ordered (meaning that e.q. permutations with $\pi(1) = 10$ is in this list before $\pi(1) = 2$).

1) Find position of specified permutation in that list - e.g. input is (1, 2, 4, 3, 5) and find position, it would give 3

2) Find what permutation lies in that list on specified position - e.g. input is 3 and I should find what permutation is on third line, that can be something like (1, 2, 4, 3, 5)

I tried to approach this as counting permutations that can be before specified one, but it seems quite complicated since $k$ can be huge number... at least for me as a combinatorics newbie.

Is there maybe some approximation that would give me some decent starting point from which I'd be able to start checking permutations manually and not having exponential time complexity?

Thanks a lot!

Answer 1

I don't think your example of $14523$ is the third one. There are $12345,12354,13245,13254$ and more before it.

We will use lexicographic ordering, where the numbers maintain their usual order. After doing what I suggest, sort your list into alphabetic order and apply that permutation to the output. The key is to recognize that there are $(k-1)!$ permutations that begin with $1$ because you can order the remaining $k-1$ numbers however you want. There are $(k-1)!$ beginning with each number.

For 1) if the first number is $m$ there are $(m-1)(k-1)!$ permutations that start with a lower number. Delete the $m$ from your permutation, reduce all the numbers greater than $m$ by $1$ and you have the same problem with a permutation of length $k-1$. Call this routine with that permutation and add its result to $(m-1)(k-1)!$

For 2) if $m$ is the position on the list the first number is $\left\lfloor \frac {m-1}{(k-1)!}\right\rfloor +1$ where the $-1$ and $+1$ come because we start counting at $1$, not $0$. Again, strip off the first number and you have a problem with $k-1$ numbers, so call the routine again.