组合数学中的全排列生成算法完整版.pdf

组合数学全排列生成算法 组合数学中的全排列深成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下 6 种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。 不论是哪种全排列生成算法，都遵循着“原排列”→“原中介数”→“ 新中介数”→“ 新排列”的过程。 其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应 性的证明我们不做讨论，这里仅仅给出了排列和中介数的详细映射方法。相信熟练掌握了方法就 可以顺利通过这部分的考察。  递增进位制和递减进位制数 所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见 到的都是固定进制数字，如2 进制，10进制等。m 位 n 进制数可以表示的数字是 m*n 个。而 m 位递增或递减进位制数则可以表示数字 m!个。例如递增进位制数4121，它的进制从右向左 依次是 2、3、4、5。即其最高位（就是数字4 那位）最大值可能是4；第三高位最大可能是3； 第二高位最大可能是 2；最末位最大可能是1。如果将4121 加上 1 的话，会使最末位得到0， 同时进位；第二位的2 与进位相加，也会得到0，同时进位；第三位的 1 与进位相加得到2， 不再进位。最终得到结果是4200 。递减进位制的道理是一样的，只不过进制从右向左依次是9、 8、7、6……，正好与递增进位制相反。很明显，递减进位制的一个最大的好处就是加法不易进 位，因为它在进行加法最频繁的末几位里（最右边）进制比较大。 接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作 一个有序的数字集合。如果规定递增进位制和递减进位制数的 0 的序号是十进制0，递增进位制 数的987654321 和递减进位制数的123456789 对应十进制序号 362880 （即9!），则可以 整理一套对应法则。其中，递增进位制数（a a a a a a a a a ）为： 1 2 3 4 5 6 7 8 9 a *9! + a *8! + ….+ a *2! + a *1! = 序号 1 2 8 9 例如序号100 的递增进位制数就是4020，即4*4 ！+ 0*3 ！+ 2*2 ！+ 0*1 ！=100。将一个序号转 换成其递增进位制数首先需要找到一个比序号小的最大阶乘数（即1、2、6、24、120、720„„）， 对其进行整数除得到递增进位制的第一位；将除法的余数反复应用这个方法（当然，之后选择的 余数是小一级的阶乘数），直到余数为0。 递减进位制数 （a a a a a a a a a ）为： 1 2 3 4 5 6 7 8 9 (((((((((a * 1 + a ) * 2 + a ) * 3 + …… + a ) * 8 + a ) * 9 + a = 序号 1 2 3 7 8 9 例如序号100 的递减进位制数就是131 （a7 a8 a9， 即从后对齐），即 （1*8 + 3）*9 + 1 = 100。将一个序号转换成其递减进位制数，需要对序号用9 取余数，就可以得到递减进位制的 最末位（这点和递增进位制先算出最高位相反）。用余下的数的整数除结果重复此过程（当然， 依次对8、7、6……取余），直到余数为0 。 关于递增进位制和递减进位制需要注意的重点：一是其加减法的进位需要小心；二是序号和数字 的转换。除了100 之外，常见的转换有：999 的递增数是121211，递减数是1670；99 的递 增数是4011 ，递减数是 130。大家可以以此为参考测试自己是否真正理解了计算的方法。下文 将省略递增进位制或递减进位制的详细计算过程。 从现在开始我们将详细介绍六种排列生成算法。具体的理论介绍将被忽略，下文所注重的就是如 何将排列映射为中介数以及如何将中介数还原为排列。我全部以求839647521 的下100 个排 列为例。  字典全排列生成法 映射方法：将原排列数字从左到右（最末尾不用理会），依次查看数字右侧比其小的数字有