Project Euler 24 (Python)

· Elliott · Project Euler, Python Solutions No comments - Tags: , ,

Question 24 from Project Euler:

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? 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import time, math
start = time.time()
 
def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)
 
target = 1000000
answer = []
digits = range(10)
nDigits = len(digits)
#the sorted permutation list will have 10! = 3628800 permutations
#solve a digit at a time
#narrowing the target and crossing off digits
while len(digits) != 1:
    x = factorial(nDigits-1)
    y = int(math.ceil(target/float(x)))
    answer.append(digits[y-1])
    digits.remove(digits[y-1])
    target -= x*(y-1)
    nDigits -= 1
#avoid being off by one digit
answer.append(digits[0])
 
print ''.join(map(str, answer))
 
print time.time()-start