yukirock
2013-09-21 02:16:36 +08:00
《组合数学》中提到过一种全排列升成算法。
给定一个整数 k，在其上方标记一个左箭头或右箭头以示方向，如：
< >
k 或 k
对于 {1..k} 的一个排列，对于其中每一个数都给定一个方向。如果一个整数 k 的箭头指向一个与其相邻但是比它小的整数，那么 k 即为「活动的」。例如对于
>>><>>
263154
356 是活动的。
可以得出如下结论：
* 1 一定不是活动的，因为 1 是最小的整数。
* 除了以下两种情况，{1..n} 中最大的整数 n 总是活动的：n 在最左边且它的箭头朝左，或 n 在最右边且它的箭头朝右。
算法如下。
从
<<..<
12..n
开始。
当存在一个活动的整数时，执行：
1. 求出最大的活动整数 m
2. 交换 m 及其箭头所指的与其相邻的整数
3. 交换所有满足 p>m 的整数 p 的方向。
以 n=4 为例：
<<<<
1234
<<<<
1243
<<<<
1423
<<<<
4123
><<<
4132
<><<
1432
<<><
1342
<<<>
1324
<<<<
3124
<<<<
3142
（略）
<<>>
2134
到 2134 中没有活动整数，算法终止。此时已经打出 {1234} 的全排列。