文档介绍：全排列的生成算法
2008年04月25日星期五下午03:23
全排列的生成算法就是对于给定的字符集， 用有效的方法将所有可能的全排列无重复无遗漏
地枚举出来。任何 n个字符集的排列都可以与 1〜n的n个数字的排列一一对应，因此在此
就以n个数字的排列为例说明排列的生成法。
n个字符的全体排列之间存在一个确定的线性顺序关系。所有的排列中除最后一个排列外，
都有一个后继；除第一个排列外，都有一个前驱。每个排列的后继都可以从 它的前驱经过
最少的变化而得到，全排列的生成算法就是从第一个排列开始逐个生成所有的排列的方法。
全排列的生成法通常有以下几种：
字典序法
递增进位数制法
递减进位数制法
邻位交换法
n进位制法
递归类算法
字典序法
字典序法中，对于数字 1、2、3……n的排列，不同排列的先后关系是从左到右逐个比较对
应的数字的先后来决定的。例如对于 5个数字的排列12354和12345，排列12345在前，
排列12354在后。按照这样的规定， 5个数字的所有的排列中最前面的是 12345，最后面
的是54321。
字典序算法如下：
设 P 是 1 〜n 的一个全排列：p=p1p2 pn=p1p2 pj-1pjpj+1 pk-1pkpk+1 pn
1） 从排列的右端开始，找出第一个比右边数字小的数字的序号 j （j从左端开始计算）， 即 j=max{i|pi<pi+1}
2） 在pj的右边的数字中，找出所有比 pj大的数中最小的数字 pk，即k=max{i|pi>pj}（右边
的数从右至左是递增的，因此 k是所有大于pj的数字中序号最大者）
3） 对换 pi, pk
4） 再将 pj+1 pk-1pkpk+1pn 倒转得到排列 p'=p1p2.•…pj-1pjpn.•…pk+1pkpk-1.•…pj+1 ,
这就是排列p的下一个下一个排列。「
例如839647521是数字1〜9的一个排列。从它生成下一个排列的步骤如下： 自右至左找出排列中第一个比右边数字小的数字 4 839647521
在该数字后的数字中找出比 4大的数中最小的一个 5 839647521
将5与4交换
839657421
将7421倒转
839651247
所以 839647521
的下一个排列是 839651247。
程序代码如下：
Private Sub Dict(p() As In teger, ByVai n As In teger)
Dim i As In teger, j As In teger
OutL p
i = n - 1
Do While i > 0
If p(i) < p(i + 1) The n
For j = n To i + 1 Step -1 ' 从排列右端开始
Next
Swap p(i), p(j)
'将递减子序列前的数字与序列中比它大的第一个数交换
For j = n To 1 Step -1
' 将这部分排列倒转
i = i + 1 ]
If i >= j The n Exit For
Swap p(i), p(j)
Next
OutL p
' 输出一个排列
i = n
End If