Prob 0024 ‐ Lexicographic Permutations - maccergit/Euler GitHub Wiki

Since the number of permutations is $N!$, we know the total number of permutations for the digits 0-9 is $10! = 3628800$, which is a number we can deal with. A little inspection also reveals that if you iterate through the elements for the first position in the permutations, you can concatenate the permutations of the remaining elements to get the total permutations :

P(0..9) = (0 + P(1..9)) \cup (1 + P(0, 2..9)) \cup \cdots \cup (9 + P(0..8))

01

The direct approach is to implement the recursive definition, generate all the permutations in order, and grab the millionth item. Since we always generate all the permutations into a list, and then pull the item we need from the list, it always takes a bit over 7 seconds to find the answer :

02

Being a recursive function that would repeatedly recompute the same subset of permutations, this is a candidate for memoization. This version runs about 7x faster :

03

The itertools library has a function to compute permutations, and this optimized library runs in a bit under a second :

04

A bit of research into permutations leads to the use of the "factoradic" to generate permutations, and it allows us to generate a specific permutation without computing all the permutations before it. While complicated, it is several orders of magnitude faster than generating all of the permutations (note that these times are in µsec, not seconds) :