Finding the 'n'th k-permutation of a set, and finding 'n' for a given k-permutation (lexicographical ordering)

Question

Suppose you have a set, and want to order the k-permutations of the set (for example, the permutations of 5 elements of the set {1, 2, 3, ..., 16}). Is there a fast way of finding 'n' (the "lexicographical index") for, say {3, 16, 4, 11, 7}, and a fast way of finding the 5-permutation such that n = 100000?

Answer 1

When you say fast, what do you mean? If you mean a faster way than actually compute all the k-permutations, you actually can treat the problem as finding some element in a base(here the basis coefficients are gonna be Permutation numbers).For example, if you give me the set $[p]=\{1,\ldots ,p\}$, an integer q and an index i you must iteratively compute $\lfloor \frac{i}{\binom{p-n-1}{q-1-n}*(q-1-n)!} \rfloor+1$ (where $\binom{p-n-1}{q-1-n}*(q-1-n)!$ states because you want to choose the other numbers that are gonna be in the sequence and they have an order)and then decrement i in the residue.
For example, suposse you want to calculate the 837th 3-permutation of $[16]$. The first element would be $\lfloor \frac{837}{\binom{16-0-1}{3-1-0}*(3-1-0)!}\rfloor +1= \lfloor \frac{837}{\binom{15}{2}*2!}\rfloor+1=\lfloor \frac{837}{210}\rfloor+1=4$
then you update the i as $837-210*\lfloor \frac{837}{210}\rfloor=207$
$\lfloor \frac{207}{\binom{16-1-1}{3-1-1}*(3-1-1)!}\rfloor +1= \lfloor \frac{207}{\binom{14}{1}*1!}\rfloor+1=\lfloor \frac{207}{14}\rfloor+1=15$ but you put 4, so it's gonna be 16.
update i as $207-14*\lfloor\frac{207}{14}\rfloor=11$ but because you put 4,it's gonna be 13. So the 3-permutation in $[16]$ with index 837 is $\{4,16,13\}$.
I think the complexity is gonna be $O(p*q)$.
For the inverse problem its the same Suposse i give $(a_1,\ldots a_q)$, the index of that permutation in $[p]$ is going to be like $(a_1-1)*\binom{p-1}{q-1}*(q-1)!+(a_2-1-[a_1<a2])*\binom{p-2}{q-2}(q-2)!+\ldots+(a_q-1-|\{j:a_j<a_q\}|)*\binom{p-q}{q-q}*(q-q)!$ I think this must be $O(p*q)$ also because of the binomial numbers.