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
-
个数全排列共有
种排列方式。本题中，如果第一个数确定了，则有
种可能排列结果。那么，第
个排列的第一个数字必然是0。
-
，所以第1000000个排列的第一个数字是2。
- 题目转换为，求数字0，1，3，4，5，6，7，8，9组成的排列中第
个排列是多少。如此递归下去即可得到结果。
- 关于为什么要 - 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)
