Project Euler Problem 24: Lexicographic Permutations¶
The source code for this problem can be found here.
Problem Statement¶
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:
What is the millionth lexicographic permutation of the digits \(0, 1, 2, 3, 4, 5, 6, 7, 8\) and \(9\)?
Solution Discussion¶
I do not see an obvious closed-form solution to this problem, I will find the answer computationally. Python provides
powerful permuted iterators that make this task very simply. The itertools module will be used to simply iterate
over the permutations of the digits \(0\) through \(9\) until the millionth element is reached. The digits in
this element will then be translated into a big-endian integer, this corresponds to the millionth number in the
sequence.
Solution Implementation¶
from itertools import islice, permutations
def solve():
""" Compute the answer to Project Euler's problem #24 """
target = 1000000
range_limit = 10
digit_permutations = permutations(range(range_limit))
digits = next(islice(digit_permutations, target - 1, target))
answer = sum([digit * 10 ** (range_limit - 1 - i) for i, digit in enumerate(digits)])
return answer
expected_answer = 2783915460
-
solutions.problem24.solve()¶ Compute the answer to Project Euler’s problem #24