Problem 24

Problem 24

16 August 2002

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?    

def fun24():
    digits = range(10)
    result = []
    count  = 1000000
    index  = 0
    while count > 0:
        t = reduce(mul, range(1, len(digits)))
        if count < t:
            result.append(digits[index])
            digits.remove(digits[index])
            index = 0
        elif count == t:
            result.append(digits[index])
            digits.remove(digits[index])
            digits.reverse()
            result += digits
            break
        else:
            index += 1
            count -= t
    return "".join(map(str, result))

count就是需要求出的第count排列组合
answer is 2783915460