Project Euler Solution 24: Lexicographic permutations
Today I have Problem 24 as part of the Project Euler series. It is about permutations and I'll use the itertools library to solve it in four lines.
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?
I have done it with the itertools library. There we have
itertools.permutations which will just generate all the permutations that can be formed. We take a slice with the millionth term (zero based indexing in Python, so 999,999). Once we have that, we just need to form that into an integer. Done.
def solution_itertools() -> int: digits = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] permutations = itertools.permutations(digits) millionth = next(itertools.islice(permutations, 999_999, 1_000_000)) return int(''.join(map(str, millionth)))
That takes 20.359 ms to execute.
The itertools library is perfect for most of your combinatoric needs and other iterator needs beyond that. I can really recommend to take a look at it!