文章目录

全排列生成算法一 钟声里的全排列**思考**：生成算法 二 字典序法1.递归2.字典序法例1：生成字母abc的全排列例2：生成123的全排列例3：生成839647521的全排列 3.**思考**：局部连续变化 三 SJT算法（Steinhaus–Johnson–Trotter algorithm）1. 引出思路2. 可移动数(mobile integer)：3. SJT算法 四 程序支持与STIRLING数1. 程序支持2. stirling数3.思考：更快更好的全排列生成算法？

全排列生成算法

计算机权威参考书：Donald E.Knuth 《计算机程序设计艺术》

一 钟声里的全排列

16，17世纪在英国兴起以固定次序鸣响一套教堂钟楼（包括5-12个钟）的方法。每口钟由一人鸣响。其变化规定为数序，例如12345，21345，23145等。

quiz：三一教堂12口编钟的变换钟乐有多少不同的曲子？

P(12,12)

思考：生成算法

怎样生成这么多的全排列？

二 字典序法

全排列的生成算法就是从第一个排列开始逐个生成所有排列的方法。

1.递归

采用递归的思想：由$\{1,2,3\dots n-1\}$的排列生成$\{1,2,3\dots n\}$的排列。如下图所示。 缺点：内存消耗大，时间复杂度高。

2.字典序法

每个排列的后继都可以从它的前驱经过最少的变化获得。

中心思想：保持尽可能长的共同前缀，变化限制在尽可能短的后缀上。

例1：生成字母abc的全排列

abc的下一个序列是acb（后继比前驱大一点），acb的下一个序列是bac，bac的下一个序列是bca，bca的下一个序列是cab，cab的下一个序列是cba。如下图：

例2：生成123的全排列

如下图所示：

基本思想：123从右向左扫描，找到第一次下降的位置，3到2下降，则交换3，2，形成132，同理扫描132，3到1下降，找后缀中比当前位置大的最小数2和1交换，形成231，要保证后缀最小则需要3，1再次交换，得到213，依次类推得到从右向左扫描依次递增的序列321，得到所有全排列的结果。如下图所示

例3：生成839647521的全排列

产生839647521在字典序中的下一个排列是839651247，推理过程如下图所示。

3.思考：局部连续变化

通过字典序法，后缀变化较多，怎样通过微小变化得到下一个排列？

三 SJT算法（Steinhaus–Johnson–Trotter algorithm）

1. 引出思路

因为递归方法，每次产生新的排列总是局部的变化，三维空间来看轨迹连续，如下图所示：

从递归的思路出发，由$\{1,2,3\}$全排列得到$\{1,2,3,4\}$全排列，如下图

不难发现：

数字具有移动的方向 每次交换两个相邻的数字 最大的能移动的数字发生交换

2. 可移动数(mobile integer)：

$\{1,2,3\dots n\}$每个数具有一定的移动方向。 如果该数的方向指向的相邻数比该数小的话则称该数是可移动数。

例如：263154按图中指向，可移动数为6 3 5.

3. SJT算法

思路：4按照箭头指向为最大可移动数，依次与3 2 1进行交换至最左端得到4 1 2 3，此时不可移动，按照指向3为最大可移动数，与2交换得到4 1 3 2，箭头指向改变，4重新变为最大可移动数，依次移动到最右端，得到1 3 2 4，以此类推，得到最终的全排列。

四 程序支持与STIRLING数

1. 程序支持

java:

算法介绍：

学术界：

常用排列生成工具

#include \<algorithm> bool next_permutation(iterator start,iterator end); bool prev_permutation(iterator start,iterator end);

实际上一般情况下n！的数量级是非常可怕的。

2. stirling数

未使用$n!$的累乘的方法，而是用近似的解析方法能够近似的逼近$n!$。

以60为例:

60个字符的全排列，按照计算机每秒生成$10^7$个排列的计算机需要的时间是多少？ $$T=60!/(365\times 24\times 3600\times 10^7)=2.65\times 10^{6}7年$$ 所以，$n!$增长速度非常快。

3.思考：更快更好的全排列生成算法？