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 210What is the millionth lexicographic permutation of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8 and 9?
This one was fun.
from math import factorial @print_timing def problem24(n): """ Determine the nth lexicographic permutation of 0123456789 """ answer = "" digits = [0,1,2,3,4,5,6,7,8,9] for i in range(9,-1,-1): ifact = factorial(i) digit = (n-1) / ifact answer += str(digits.pop(digit)) n = n - (digit * ifact) return answer >>> problem24(1000000) problem24 took 0.000 ms '2783915460' >>> |
Tags: permutations, problem24, project euler, python