Project Euler 24 Lexicographic permutations

Question

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?

Analysis

1. 个数全排列共有种排列方式。本题中，如果第一个数确定了，则有种可能排列结果。那么，第个排列的第一个数字必然是0。
2. ，所以第1000000个排列的第一个数字是2。
3. 题目转换为，求数字0，1，3，4，5，6，7，8，9组成的排列中第个排列是多少。如此递归下去即可得到结果。
4. 关于为什么要 - 1，很难解释清楚，但是根据推理很容易得到。10个数字组成的第一个排列应该是 0123456789，如果不减1，带入到代码中得到的会是 0123456798。

Program

number_order = 1000000
length = 10

max_factor = 3628800  # the factorial of 10
num_list = list(range(length))
rst = []

number_order -= 1
while len(num_list) > 0:
    max_factor //= len(num_list)
    integer = number_order // max_factor
    rst.append(num_list.pop(integer))
    number_order %= max_factor

print(rst)