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)