024. 字典排列(Lexicographic permutations)
一个排列是某些对象的有序组合，例如，3124就是数字1，2，3，4的一种可能排列。如果所有排列按数字从小到在与或者字母表从前到后的顺序排列，我们称其为字典排列。数字0，1，2的字典排列为：012，021，102，120，201，210。从零到九的所有数字构成的字典排列中，第一百万个数字是多少？
分析：为了对简化叙述，我们先看一个简单的情形：求由0,1,2,3构成的字典排列中第十个是多少？显然四个数可以形成的排列有\(4!=24\)种。由于字典排列是从小到大排列的，那么先看首位是零的情况，固定首位是零，则剩下三位共有\(3!=6\)种情况，既然要求第十个数，则首位必然是零，又因为首位是一的排列也有六种，所以第十个数的首位必然是一，且应该处于以一为首位的数字的第四位(十除六余四)。接下来我们要考虑的是在由0,2,3构成的字典排列中找到第四位，这个数是230，则所求的数应该是1230。这里我们可以看到，我们实际上把所求问题分解成了一个小规模的问题，即把求0,1,2,3构成的字典排列第十个数的问题，转化为求0,2,3构成的字典的排列中第四个数的问题。因此，这个问题可以使用动态规划的方式求解。
假设要求从零到九的数构成的字符串\(S\)形成的字典排列中的第\(n\)位，记为\(lp(n,s)\)。字符串的长度为\(len(s)\)，设\(q=n/(len(s)-1)!,\ r=n\%(len(s)-1)!\)，则我们可以将动态规划的状态转移方程表述为：
$$
lp(n,s)=
\begin{cases}
s[q]+lp(r,s[:q]+s[q+1:]) & len(s)>1\\
s & len(s)=1
\end{cases}
$$
这个状态转移方程只是开头介绍的推理思路的一般化，核心是要把原问题逐步分解，化简成我们易于处理的问题。代码实现如下：
# time cost = 280 ns ± 1.51 ns
from math import factorial as fac
from functools import lru_cache
@lru_cache(maxsize=128)
def nth_lexi_perm(n,s):
if len(s) == 1:
return s
else:
q,r = divmod(n,fac(len(s)-1))
return (s[q] + nth_lexi_perm(r,s[:q]+s[q+1:]))
def main(n=10**6,s='0123456789'):
return nth_lexi_perm(n-1,s)