产生排列的算法

win_hate

以前在这里曾讨论过产生排列的算法，最近学到一个新的方法，放在这里跟大家分享。据 Sedgewick 说，这个算法产生的排列顺序是以前英国教堂敲钟时采用的，我们不妨称之为敲钟序。

两个旧文的连接：

[CU,cC,algo] Generate Permutation
http://www.cublog.cn/u/u/20/showart.php?id=58107

[algo] 产生全排列的算法
http://www.cublog.cn/u/20/showart.php?id=58123

先举一个例子，产生 1，2，3 的全部排列：

1 2 3 4    1 2 3    1 2    1
1 2 4 3
1 4 2 3
4 1 2 3

4 1 3 2    1 3 2
1 4 3 2
1 3 4 2
1 3 2 4

3 1 2 4    3 1 2
3 1 4 2
3 4 1 2
4 3 1 2

4 3 2 1    3 2 1    2 1    1
3 4 2 1
3 2 4 1
3 2 1 4

4 2 3 1    2 3 1
2 4 3 1   
2 3 4 1
2 3 1 4

4 2 1 3    2 1 3
2 4 1 3
2 1 4 3
2 1 3 4


想法并没有什么新颖的，在以前的帖子中已经说过，生成排列可以递归着做，把 n 通过 n 种不同的方式插入 1...n-1 的排列。但在实现递归时，可以做得很巧妙。

1 2 3 4 包含 1 的一个排列; 1-2 的一个排列； 1--3 的一个排列；移动 4 则得到 1 2 3 基础上得到的 1--4 排列， 最后状态为 4 1 2 3。

若能得到 1 2 3 的下一个 1--3 排列，则把 4 反向移动可以得到新的 1--4 排列。若能得到全部的 1 2 3 排列，则按此方法能得到全部 1--4 排列。

1 2 3 的全部排列可以这样得到：先移动 3，得到 1 2 基础上的 1--3 排列；再去 1 2 的下一个 1--2 排列，再把 3 晃回来 ......

如是最终得到全部的 1--4 排列。


对 1-n 排列，我们可以设计这样一个模型，n 个元素，对应 n 个齿轮，编号为 1 到 n, 第 i 个齿轮有可以正转 i 步，再反转 i 步，活动范围为 [1，i]。齿轮中带有状态，记录了 n 个元素在排列中的具体位置、齿轮位置、齿轮转动方向。

齿轮组的初始状态为：i 齿轮处于正转了 i 步的状态，现方向为逆转（即准备反转了），i 元素在排列中的第 i 个位置（即排列初始态为 1...n）

工作方式为：

从序号最大的齿轮开始，交替运作，每次最多动一个齿轮，第一个齿轮转动范围为 [1,1]，即不能转动，一旦把控制权交给齿轮 1，则停机。

1 若齿轮未转到尽头，则按方向转动一下。调整 n 元素的排列，输出。把控制权转给最大序号的齿轮
2 若齿轮已在尽头，按原方向已经不能转动，则不转动，并把方向反转，控制权叫给序号小一的齿轮
3 若控制权交给齿轮 1，则停机器。

[注释]
i 齿轮不能转动时，表明在该 1--(i-1) 排列基础上得到的 1--i 排列已经全部给出，需要新的 1-(i-1) 排列。所以把控制权交给 i-1 齿轮， i-1 齿轮转动得到新的 1--(i-1) 排列....

i 齿轮能转动时，要产生在此基础上的 1--(i+1)...(1--n) 排列，所以把控制权交还给齿轮 n.

这个算法不错的，偶尔停顿，几乎每一步都交换两个元素，产生一个新排列。停顿（设置反向）次数为
(n-1)!+...+2!+1, 相比起产生 n! 个排列来，似乎不算太多。

代码见后，我在一台旧机器上计算 10 个元素的全排列，颇算了一阵，但不算太久。

$ ./a.out 10 > log

$ du -h log
39M log

$ wc -l log
3628800 log

$ cat log |sort |uniq |wc -l
3628800

$ echo '10!;' |maple -q
                                    3628800


可见生成的排列各不相同，代码基本正确。

[代码]

[ 本帖最后由 win_hate 于 2006-2-23 12:12 编辑 ]

dbcat

原帖由 win_hate 于 2006-2-22 12:30 发表
以前在这里曾讨论过产生排列的算法，最近学到一个新的方法，放在这里跟大家分享。据 Sedgewick 说，这个算法产生的排列顺序是以前英国教堂敲钟时采用的，我们不妨称之为敲钟序。

两个旧文的连接：

[CU,c ...

如果是全排列的话也可以用SHELL：
echo {1,2,3}{1,2,3}{1,2,3}
就可以产生1，2，3的全排列，当然还得筛选。
但是如果排列元素很多的话，就得用C了，
SHELL的效率不行。

[ 本帖最后由 dbcat 于 2006-2-22 12:48 编辑 ]