排列的生成算法

组合数学 数学

虽然书上的标题写的是 "排列的生成算法", 但实际上貌似只有"全排列的生成算法".

求当前排列的下一个排列

本来想宇宙惯例先抄一段书, 结果发现书上写的及其啰嗦....还是我自己解释吧.

我们先重定义一下 "前缀" 和 "后缀".
在这里, 一个排列的 "后缀" 指的是该排列从后往前的一个连续上升序列,
"前缀" 则是这个排列删除它的后缀后的部分.
例如, 839647521 的后缀是 "7521", 前缀就是 "83964".

下面我就结合 839647521 这个排列来介绍一下我们的做法.

1. 把当前排列和它的后缀切除, 变为 "83964" 和 "7521".
2. 我们在它的后缀中找到最后一个比 它的前缀的最后一个数大 的数, 这里就是 "5".
3. 把这两个数调换, 这样, 它的前缀和后缀就分别变为 "83965" 和 "7421".
4. 把后缀翻转 (其实就是从小到大排个序), 再把 新前缀 和 新后缀 拼在一起, 就得到了当前排列的下一个排列 "839651247".

为什么是正确的呢, 我们来感性理解一下.

找比当前排列的序号(排名)更大的排列, 其实就是要用一个后面的数替换前面的一个比它小的数,

那么为了找到当前排列的下一个排列, 就要保证这个新排列的序号恰好比原排列的序号大 1 (废话),

那当前排列的后缀中的数显然是不能互相交换的, 不然新排列就会比原排列更小,

所以我们就要找到第一个能够与后缀中的数交换的数, 然后用后缀中尽可能小的数来替换它,

替换之后, 新序列已经比原序列大了, 那么为了保证它恰好比原序列大, 那么就将它的后缀排个序. 由于后缀是(从前往后)递减的, 所以我们只需将它翻转一下就行了.

这样, 我们就可以 口胡 理解这个方法的正确性了.

求当前排列的序号

这个内容书上好像没有, 是我们老师上课时候讲的.

先上公式吧.

设当前排列为 $p_1,p_2,p_3,\cdots,p_n$, 定义 $k_i$ 为 $p_i$ 右边比 $p_i$ 小的数的数量, 即 $|S_i|,S_i=\{p_j\mid j>i,p_j<p_i\}$.
当前排列的序号为

还是结合例子来理解吧, 设当前序列为 83967521.
那么它的序号其实就是前缀先于 83967521 的排列个数+1, 我们记为 $pre(83967521)+1$.
(PS : 这里的"前缀"不是前面重新定义的"前缀".)

那么我们一步一步来考虑, 先求前缀先于 8 的排列数,
那我们就保证排列的第一位小于 8, 剩下的八位就可以随便排了, 所以

$pre(8)=7*8!. \\ $

继续, 求前缀先于 83 的排列数,
这时, 第一位就可以取 8 了, 我们只要保证第一位取 8 时第二位小于 3 就行了, 所以有

$pre(83)=pre(8)+2*7!=7*8!+2*7! \\ $

前缀为 839 时也一样, 只不过当第一位和第二位分别为 8 和 3 时, 由于 8 已经被选了, 第三位就不能取 8 了, 所以

$pre(839)=7*8!+2*7!+6*6!. \\ $

最后得到

$pre(839647521)=7*8!+2*7!+6*6!+4*5!+2*4!+3*3!+2*2!+1*1!+0*0!=297191. \\ $

所以排列 839647521 的序号为 297192.