Finding the n-th lexicographic permutation of a string

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]

Yes, I figured it out. My approach was correct, but I took the wrong number at 1*4!. Silly mistake.

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)