Finding the n-th lexicographic permutation of a string 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?
 A: Yes, I figured it out. My approach was correct, but I took the wrong number at 1*4!. Silly mistake.
A: I think the above solutions are slightly off. The $k$-th permutation $P_k$ of a string $S$ can be computed as follows (assuming zero-based index):


*

*$P_k := \epsilon$

*while $S \neq \epsilon$:


*

*$ f := (|S|-1)!$

*$i := \lfloor k/f\rfloor$

*$x := S_i$

*$k := k \bmod f$

*append $x$ to $P_k$

*remove $x$ from $S$


*return $P_k$


Essentially, this finds the first element of the k-th permutation of S, and then recurses on the remaining string to find its first element.
Depending on whether you start counting your permutations from 0 or 1, the answers is $(2, 7, 8, 3, 9, 1, 5, 6, 0, 4)$ or $(2, 7, 8, 3, 9, 1, 5, 6, 4, 0)$.
Here's a little Python code, implementing the algorithm above as well as its recursive version, then checking correctness for $\vert S\vert=10$ (this might take some time to run):

from math import factorial, floor

# compute the k-th permutation of S (all indices are zero-based)
# all elements in S must be unique

def kthperm(S, k):  #  nonrecursive version
    P = []
    while S != []:
        f = factorial(len(S)-1)
        i = int(floor(k/f))
        x = S[i]
        k = k%f
        P.append(x)
        S = S[:i] + S[i+1:]
    return P


def kthpermrec(S, k):   # recursive version
    P = []
    if S == []:
        return []
    else:
        f = factorial(len(S)-1)
        i = int(floor(k/f))
        return [S[i]] + kthpermrec(S[:i] + S[i+1:], k%f)


if __name__ == "__main__":
    # This creates the k-th permutations for k=0..len(S)!, and then checks that the result is indeed in lexicographic order.

    nrElements = 10
    printout = True
    result = [] # the list of permutations
    for k in xrange(factorial(nrElements)): # loop over all k=0..len(S)!
        S = range(nrElements)    # [0, 1, 2, 3, ... , nrElements-1] 
        p1 = kthperm(S, k)    # compute k-th permutation iteratively
        p2 = kthpermrec(S, k)    # compute k-th permutation recursively
        assert p1==p2       # make sure the recursive and non-recursive function yield the same permutation
        if printout:
            print p1
        result.append(p1)    # add to list of permutations

    for i in xrange(len(result)-1):    # check that permutations are in lexicographic order.
        assert result[i] < result[i+1], "Permutations are not sorted, the code is incorrect."
        assert len(set(result[i])) == len(result[i]), "Permutation contains multiple copies of an element, the code is incorrect."
    assert len(set(result[-1])) == len(result[-1]), "Permutation contains multiple copies of an element, the code is incorrect."    # check on last element
    print "The code is correct for |S| = %d." % nrElements    # This line is only reached if no assertion failed, i.e. all permutations are in lexicographic order.


    print kthperm(range(10), 1000000)
    print kthperm(range(10), 1000001)

A: 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]

A: If you need a tester program that calculate permutation from index or viceversa, you can see here. 
It can be useful and it's easy to use. It's based on factoradic.
As example:
it allows to calculate the correct index corresponding to the solution "2783905614" mentioned earlier
Or
obtain the 2,000,000th permutation of S = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } )
It works up to 17 elements (max index = 355,687,428,096,000)
