Euler Solution 24

From ProgSoc Wiki

Jump to: navigation, search

What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?

Solutions to Problem 24

Python by Althalus

(Original version had a slight bug, fixed by tomchristmas)

import time

"""
This one was painful...
for 10 numbers, they can be arranged 10! ways.
If we fix the first number, then we have 9! ways.
At this point we need the 1000000th permutation of 10 digits.
int(1000000/9!) =2. This tells us that from a list of [0,1,2,3,4,5,6,7,8,9]
We want the 3rd element. (list[2])
Now we want the (1000000-(9!*2))th permutation of 9 digits.
And so on and so forth.
"""

"""
Factorial library function doesn't seem to be available on niflheim, so
I've implemented a factorial function here - my first ever
scrap of python code! - tomchristmas
"""

def factorial(n):
    if n > 0:
       return n * factorial(n - 1)
    else:
       return 1

start_time = time.time()
result = []
source = [0,1,2,3,4,5,6,7,8,9]
lex = 1000000
while len(result) < 10:
    h = factorial(len(source)-1)
    i = int(lex/h) 
    if lex-(i*h)> 0: lex -= int(i*h)

    """Bug fix"""

    if len(source) < len(result):
       if i >= len(source):
          i = len(source) - 1
       else:
          i = len(source) - i
    else:
       if i >= len(source):
          i = len(source) - 1

    result.append(source.pop(i))
print(result)
run_time = time.time() - start_time
print(run_time)
Personal tools