Combinatorics – Finding the n-th Lexicographic Permutation of a String

combinatoricspuzzle

I have an ordered set of symbols S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }. I want to find the 1,000,000-th permutation in lexicographic order of S. It is a programming puzzle, but I wanted to figure out a way without brute-forcing the task.

So my thinking was like this:

For 10 variable symbol positions, we have 10! permutations, obviously. Now we want to find the first symbol.

If we fix the first symbol, then the remaining 9 symbols can have 9! combinations.

That means that 0 or 1 cannot be the first symbol, because the highest possible position is 2*9! = 725,760, which is lower than 1,000,000.

The lowest position for a leading 3 is 3*9! + 1 = 1,088,641, so it can't be 3 or higher, either.

Therefore, the first number must be 2. 2*9! is the largest multiple of 9! no greater than 1,000,000, so I need the 2nd symbol (zero-based) from the current set.

So now the question becomes, of the remaining S := S \{2}, which permutation of these symbols is at lexicographic position (1,000,000 – 2*9!) = 274,240?

6*8! = 241,920 is the largest multiple of 8! which is smaller than 274,240, so I need the 6th-smallest symbol of the remaining set, which is 7. So the prefix should be 27 by now.

That way, I keep going and finally arrive at:
1,000,000 = 2*9! + 6*8! + 6*7! + 2*6! + 5*5! + 1*4! + 2*3! + 2*2! + 0*1! + 0*0!

which results in "2783905614" as my solution.

However, according to the solution tester, (free reg. req.) that is incorrect.

Where did I go wrong in thinking or applying?

Best Answer

To formalize, if $a_0 < ... < a_n$, then in the $k$-th permutation of $\{a_0, ..., a_n\}$ in lexiographic order, the leading entry is $a_q$ if $k = q(n!) + r$ for some $q\ge0$ and $0<r\le n!$. (Note that the definition of $r$ here is a bit different from the usual remainder, for which $0\le r< n!$. Also, $a_q$ is the $(q+1)$-th entry but not the $q$-th entry in the sequence, because the index starts from 0.)

    [0 1 2 3 4 5 6 7 8 9]
1000000 = 2(9!) + 274240
    2 [0 1 3 4 5 6 7 8 9]
274240 = 6(8!) + 32320
    2 7 [0 1 3 4 5 6 8 9]
32320 = 6*(7!) + 2080
    2 7 8 [0 1 3 4 5 6 9]
2080 = 2*(6!) + 640
    2 7 8 3 [0 1 4 5 6 9]
640 = 5(5!) + 40
    2 7 8 3 9 [0 1 4 5 6]
40 = 1(4!) + 16
    2 7 8 3 9 1 [0 4 5 6]
16 = 2(3!) + 4
    2 7 8 3 9 1 5 [0 4 6]
4 = 1(2!) + 2 <-- we don't write 4 = 2(2!) + 0 here; we need 0<r<=2!
    2 7 8 3 9 1 5 4 [0 6]
2 = 1(1!) + 1
    2 7 8 3 9 1 5 4 6 [0]
Related Question