组合数学中的全排列生成算法.docVIP

组合数学中的全排列深成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下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!），则可以整理一套对应法则。其中，递增进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为： a1*9! + a2*8! + ….+ a8*2! + a9*1! = 序号 例如序号100的递增进位制数就是4020，即4*4！+ 0*3！+ 2*2！+ 0*1！=100。将一个序号转换成其递增进位制数首先需要找到一个比序号小的最大阶乘数（即1、2、6、24、120、720……），对其进行整数除得到递增进位制的第一位；将除法的余数反复应用这个方法（当然，之后选择的余数是小一级的阶乘数），直到余数为0。 递减进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为： ? (((((((((a1 * 1 + a2) * 2 + a3) * 3 + …… + a7) * 8 + a8) * 9 + a9= 序号 例如序号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个排列为例。 ? 字典全排列生成法 映射方法：将原排列数字从左到右（最末尾不用理会），依次查看数字右侧比其小的数字有几个，个数就是中介数的一位。例如，对于排列839647521。最高位8右侧比8小的有7个数字，次高位3右侧比3小的数字有2个，再次位的9的右侧比9小的有6个数字，……，2的右侧比2小的数有1个。得到递增进制中介（此中介数加上100的递增进进制数4020后得到新中介 还原方法：还原方法为映射方法的逆过程。你可以先写出辅助数字1 2 3 4 5 6 7 8 9，以及9个空位用于填充新排列。然后从新中介数的最高位数起。例如新中介数最高位是x，你就可以从辅助数字的第一个没有被使用的数字开始数起，数到x。第x+1个数字就应当是空位的第一个数字。我们将此数字标为“已用”，然后用其填充左起第一个空位。然后，再看新中介数的次高位y，从辅助数字的第一个未用数字数起，数到一。第y+1个数字就是下一个空位的数字。我们将此数字标为“已用”，然后用其填充左起第二个空位。依此类推，直到最后一个中介数中的数字被数完为止。例如对于新中介数7