排列组合算法

我们都知道排列与组合的个数可以利用公式很容易的求出来，但是要是把这些排列组合的序列一一输出怎么办呢？

下面结合《组合数学》（第四版）卢开澄卢华明编著，好好总结排列与组合的算法。

一．排列的生成算法

1.1  序数法（也被称作递增进位数法）

我们都知道n个数的全排列个数是n!个。其实任何一个数都可以用阶乘的二项式来表示(严格的证明可以参考书中，连我这种菜鸟都能看懂)，如

4000 = 5*6! + 3*5! + 4! + 2*3! + 2*2!  

其中{5,3,1,2,2}就是他们的系数，系数与整数一一对应。每个整数有唯一的系数和其对应。

看到这里我们也许会猜想，要是我们每个全排列的序列都对应一个系数，那该多好！

设序数   

                       （an-1,an-2,-----a2,a1）         (1)

对应的规则如下：式1中第一个数an-1表示排列中数n的右（或左）端比n小的个数，将n排列的位置确定下来，接着取an-2，它表示在排列中n-1这个数在排列中的右（或左）端比n-1小的个数，依次类推。

   以1，2，3，4，的排列4213为例，排列4213，4的右方比它小的数有3位，故a3=3；3的右方比3小的数为0，故a2=0；2的右方比2小的数为1，故a1=1.故排列4213对应于序数（301），反过来从（301）可推的排列4213.此时，（301）被称作中介数。

下面是从网络上转载的资料，讲的比较详细：

例如排列839647521的中介数是72642321，7、2、6、......分别是排列中数字8、3、9、......的右边比它小的数字个数。     中介数是计算排列的中间环节。已知一个排列，要求下一个排列，首先确定其中介数，一个排列的后继，其中介数是原排列中介数加1，需要注意的是，如果中介数的末位kn-1+1=2，则要向前进位，一般情形，如果ki+1=n-i+1，则要进位，这就是所谓的递增进位制。例如排列839647521的中介数是72642321，则下一个排列的中介数是67342221+1=67342300（因为1+1=2，所以向前进位，2+1=3，又发生进位，所以下一个中介数是67342300）。 得到中介数后，可根据它还原对应得排列。算法如下：     中介数k1、k2、......、kn-1的各位数字顺序表示排列中的数字n、n-1、......、2在排列中距右端的的空位数，因此，要按k1、k2、......、kn-1的值从右向左确定n、n-1、......、2的位置，并逐个放置在排列中：i放在右起的ki+1位，如果某位已放有数字，则该位置不算在内，最后一个空位放1。      因此从67342300可得到排列849617523，它就是839647521的后一个排列。因为9最先放置，k1=6，9放在右起第7位，空出6个空位，然后是放8，k2=7，8放在右起第8位，但9占用一位，故8应放在右起第9位，余类推。

1.2  递减进位制数法

在递增进位制数法中，中介数的最低位是逢2进1，进位频繁，这是一个缺点。把递增进位制数翻转,就得到递减进位制数。     839647521的中介数是67342221(k1k2…kn-1)，倒转成为12224376(kn-1…k2k1)，这是递减进位制数的中介数：ki(i=n-1,n-2,…,2)位逢i向ki-1位进1。给定排列p，p的下一个排列的中介数定义为p的中介数加1。例如p=839647521，p的中介数为12224376，p的下一个排列的中介数为12224376+1=12224377，由此得到p的下一个排列为893647521。 给定中介数，可用与递增进位制数法类似的方法还原出排列。但在递减进位制数中，可以不先计算中介数就直接从一个排列求出下一个排列。具体算法如下： 1）如果p(i)=n且in，则p(i)与p(i-1)交换 2）如果p(n)=n，则找出一个连续递减序列9、8、......、i，将其从排列左端删除，再以相反顺序加在排列右端，然后将i-1与左边的数字交换 例如p=893647521的下一个排列是983647521。求983647521的下一个排列时，因为9在最左边且第2位为8，第3位不是7，所以将8和9从小到大排于最右端364752189，再将7与其左方数字对调得到983647521的下一个排列是367452189。又例如求987635421的下一个排列，只需要将9876从小到大排到最右端并将5与其左方数字3对调，得到534216789。

1.3  字典序法

假如四位数1234，我们按照从后往前开始变化，也就是按我们通常的做法进行排列：

1234，1243，1324，1342，1432，····4321

我们称它是按字典的排列顺序排列的。可以观察到初始状态是1234，每一个数都比后面一个小。最终状态为4321，每一个数都比后面一个数大。那么1234与4321之间的数肯定不是有序的.

字典序法的定义：

S1.求满足关系式pj-11，则排列P由排列(i)Pi构成（i=1、2、....、n-1）。 根据定义，容易看出如果已经生成了k-1个元素的排列，那么，k个元素的排列可以在每个k-1个元素的排列Pi前添加元素i而生成。例如2个元素的排列是1  2和2   1，对与个元素而言，p1是2  3和3  2，在每个排列前加上1即生成1 2 3和1 3 2两个新排列，p2和p3则是1  3、3  1和1  2、2  1，按同样方法可生成新排列2 1 3、2 3 1和3 1 2、3 2 1。 3）循环移位法 如果已经生成了k-1个元素的排列，则在每个排列后添加元素k使之成为k个元素的排列，然后将每个排列循环左移（右移），每移动一次就产生一个新的排列。 例如2个元素的排列是1 2和2 1。在1 2后加上3成为新排列1 2 3，将它循环左移可再生成新排列2 3 1、3 1 2，同样2 1可生成新排列2 1 3、1 3 2和3 2 1。

参考文献：

《组合数学》（第四版）卢开澄卢华明编著

 http://hi.baidu.com/applelove1990/item/ccc11937b45e6efe2684f405

http://blog.csdn.net/sharpdew/article/details/755074

http://blog.csdn.net/joylnwang/article/details/7064115