# 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?

• The solution is $2783915460$, you can find many explainations on how to get when seeing the solution-page. – Listing Aug 30 '11 at 16:32
• Shouldn't 1*4! result in a 1 digit, not 0? – Ross Millikan Aug 30 '11 at 16:39
• Won't that term $1*4!$ mean that the sixth digit shoud be $1$, not $0$? – Jyrki Lahtonen Aug 30 '11 at 16:40
• – Ilmari Karonen Aug 30 '11 at 21:54

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]

• Thanks, your scheme explains itself. – jonaprieto Jun 3 '13 at 2:40
• Nice. Wondering how the calculation would change for repeated symbols? – Abu Bakar Dec 6 '15 at 3:46

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)

• If all indices are zero-based, shouldn't you find kthperm(range(10), 999999) instead of kthperm(range(10), 1000000)? – user1551 Aug 26 '15 at 7:19

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)