A permutation is an ordered arrangement of objects. For example, 3124 is one possible permutation of the digits 1, 2, 3 and 4. If all of the permutations are listed numerically or alphabetically, we call it lexicographic order. The lexicographic permutations of 0, 1 and 2 are:
012 021 102 120 201 210
What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
To avoid pesky off-by-one errors, instead of finding the millionth permutation, I order the permutations starting from zero and try to find permutation number \(999999\).
No matter which digit we pick to begin a permutation, there will be nine left over. It follows that the \(10!\) lexicographically ordered permutations of \(\{0,1,2,\ldots,9\}\) consist of \(9!\) permutations beginning with 0, followed by \(9!\) permutations beginning with 1, followed by \(9!\) permutations beginning with 2, and so forth. Because \(2 \cdot 9! \leq 999999 < 3 \cdot 9!\), the first digit of our desired permutation is 2, and the problem reduces to finding the \((999999 - 2 \cdot 9!)\)-th permutation of \(\{0, 1, 3, 4, 5, 6, 7, 8, 9\}\).
No matter which digit we pick to begin a permutation of these numbers, there will be eight left over; so there will be \(8!\) beginning with 0, followed by \(8!\) beginning with 1, followed by \(8!\) beginning with 3, and so forth. Because \(6 \cdot 8! \leq (999999 - 2 \cdot 9!) < 7 \cdot 8!\), the next digit of our desired permutation is the 7th in the set — which is 7 — and the problem reduces to finding the \((999999 - 2 \cdot 9! - 6 \cdot 8!)\)-th permutation of \(\{0, 1, 3, 4, 5, 6, 8, 9\}\).
We work through the remaining digits in the same way. This problem is closely related to the factorial number system: every positive integer less than \(10!\) can be uniquely represented in the form \(a_9 \cdot 9! + a_8 \cdot 8! + \cdots + a_1 \cdot 1! + a_0 \cdot 0!\), where \(0 \leq a_k < k\) for all \(k\). To find the answer from the tuple \((a_9, a_8, \ldots, a_0)\) representing \(999999\), we progressively take \(k\) from 9 down to 0 and select the \((a_k + 1)\)-st digit we haven't already selected.
from math import factorial
def p24(n = 999999):
res = ""
digs = list(map(str, range(10)))
for k in range(9, -1, -1):
a = n // factorial(k)
res += digs[a]
digs = digs[:a] + digs[a+1:]
n %= factorial(k)
return res