《组合数学中的全排列生成算法完整版》由会员分享，可在线阅读，更多相关《组合数学中的全排列生成算法完整版（9页珍藏版）》请在金锄头文库上搜索。
1、组合数学全排列生成算法 组合数学中的全排列深成算法历来是组合数学考试的重要考察点， 因此在这里我简单的介绍一下 6 种全排列生成算法的详细过程，并借此比较它们之间的优劣之处。 不论是哪种全排列生成算法，都遵循着“原排列”“原中介数”“新中介数”“新排列”的过程。 其中中介数依据算法的不同会的到递增进位制数和递减进位制数。 关于排列和中介数的一一对应 性的证明我们不做讨论， 这里仅仅给出了排列和中介数的详细映射方法。 相信熟练掌握了方法就 可以顺利通过这部分的考察。 递增进位制和递减进位制数 所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。 通常我们见 到的都是固定进制
2、数字，如 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，正好与递增进位制
3、相反。很明显，递减进位制的一个最大的好处就是加法不易进 位，因为它在进行加法最频繁的末几位里（最右边）进制比较大。 接下来要了解的是递增进位制、递减进位制数和其序号的关系。递增、递减进位制数可以被看作 一个有序的数字集合。 如果规定递增进位制和递减进位制数的 0 的序号是十进制 0，递增进位制 数的 987654321 和递减进位制数的 123456789 对应十进制序号 362880（即 9!），则可以 整理一套对应法则。其中，递增进位制数（a1 a2 a3 a4 a5 a6 a7 a8 a9）为： a1*9! + a2*8! + .+ a8*2! + a9*1! = 序号 例如序号 100
4、 的递增进位制数就是 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，
5、 即从后对齐），即 （1*8 + 3）*9 + 1 = 100。将一个序号转换成其递减进位制数，需要对序号用 9 取余数，就可以得到递减进位制的 最末位（这点和递增进位制先算出最高位相反）。用余下的数的整数除结果重复此过程（当然， 依次对 8、7、6取余），直到余数为 0。 关于递增进位制和递减进位制需要注意的重点： 一是其加减法的进位需要小心； 二是序号和数字 的转换。除了 100 之外，常见的转换有：999 的递增数是 121211，递减数是 1670；99 的递 增数是 4011，递减数是 130。大家可以以此为参考测试自己是否真正理解了计算的方法。下文 将省略递增进位制或递减进位制的详
6、细计算过程。 从现在开始我们将详细介绍六种排列生成算法。 具体的理论介绍将被忽略， 下文所注重的就是如 何将排列映射为中介数以及如何将中介数还原为排列。我全部以求 839647521 的下 100 个排 列为例。 字典全排列生成法 映射方法：映射方法：将原排列数字从左到右 （最末尾不用理会） ， 依次查看数字右侧比其小的数字有几个， 个数就是中介数的一位。例如，对于排列 839647521。最高位 8 右侧比 8 小的有 7 个数字， 次高位 3 右侧比 3 小的数字有 2 个，再次位的 9 的右侧比 9 小的有 6 个数字，2 的右侧 比 2 小的数有 1 个。得到递增进制中介数 72642
7、321。（此中介数加上 100 的递增进进制数 4020 后得到新中介数 72652011） 还原方法：还原方法：还原方法为映射方法的逆过程。你可以先写出辅助数字 1 2 3 4 5 6 7 8 9，以及 9 个空位用于填充新排列。然后从新中介数的最高位数起。例如新中介数最高位是 x，你就可以从 辅助数字的第一个没有被使用的数字开始数起，数到 x。第 x+1 个数字就应当是空位的第一个 数字。我们将此数字标为“已用”，然后用其填充左起第一个空位。然后，再看新中介数的次高位 y，从辅助数字的第一个未用数字数起，数到一。第 y+1 个数字就是下一个空位的数字。我们 将此数字标为“已用”，然后用其填
8、充左起第二个空位。依此类推，直到最后一个中介数中的数字 被数完为止。例如对于新中介数 72652011，我们给出其辅助数字和空位的每一步的情况。其 中红色的数字代表“正在标记为已用”，“已用”的数字不会再被算在之后的计数当中。当新中介数 中所有的数字都被数完了， 辅助数字中剩下的唯一数字将被填入最后的空位中。 最终得到新排列 839741562。 新中介数当新中介数当 前位前位 辅助数字辅助数字 新排列数新排列数 初始 1 2 3 4 5 6 7 8 9 7 1 2 3 4 5 6 7 8 9 8 2 1 2 3 4 5 6 7 8 9 8 3 6 1 2 3 4 5 6 7 8 9 8 3
9、9 5 1 2 3 4 5 6 7 8 9 8 3 9 7 2 1 2 3 4 5 6 7 8 9 8 3 9 7 4 0 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1 1 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1 5 1 1 2 3 4 5 6 7 8 9 8 3 9 7 4 1 5 6 最后补位 8 3 9 7 4 1 5 6 2 递增进位排列生成算法 映射方法：映射方法：将原排列按照从 9 到 2 的顺序，依次查看其右侧比其小的数字的个数。这个个数就 是中介数的一位。例如对于原排列 839647521。9 的右侧比 9 小的数字有 6 个，8 的右侧比 8
10、 小的数字有 7 个，7 的右侧比 7 小的数字有 3 个，2 的右侧比 2 小的数字有 1 个。最后得 到递增进制中介数 67342221。（此中介数加上 100 的递增进制数 4020 得到新的中介数 67351311） 还原方法：还原方法：我们设新中介数的位置号从左向右依次是 9、8、7、6、5、4、3、2。在还原前， 画 9 个空格。对于每一个在位置 x的中介数 y，从空格的右侧向左数 y 个未被占用的空格。在 第 y+1 个未占用的空格中填上数字 x。重复这个过程直到中介数中所有的位都被数完。最后在 余下的最后一个空格里填上 1，完成新排列的生成。以新中介数 67351311 为例，
11、我给出了详 细的恢复步骤。其中红色数字代表新填上的数字。最后得到新排列 869427351。 新中介数新中介数 当前位当前位 新排列数新排列数 备注备注 初始 6 9 从右向左数 6 个空格，第 7 个空窭锾 睢?/span9” 7 8 9 从右向左数 7 个空格，第 8 个空格里填 “8” 3 8 9 7 从右向左数 3 个空格，第 4 个空格里填 “7” 5 8 6 9 7 从右向左数 5 个空格，第 6 个空格里填 “6” 1 8 6 9 7 5 从右向左数 1 个空格，第 2 个空格里填 “5” 3 8 6 9 4 7 5 从右向左数 3 个空格，第 4 个空格里填 “4” 1 8 6
12、 9 4 7 3 5 从右向左数 1 个空格，第 2 个空格里填 “3” 1 8 6 9 4 2 7 3 5 从右向左数 1 个空格，第 2 个空格里填 “2” 最后补位 8 6 9 4 2 7 3 5 1 余下的空格填“1” 递减进位排列生成算法 映射方法：映射方法：递减进位制的映射方法刚好和递增进位制相反，即按照从 9 到 2 的顺序，依次查看 其右侧比其小数字的个数。但是，生成中介数的顺序不再是从左向右，而是从右向左。生成的递 减进制中介数刚好是递增进位排列生成算法得到中介数的镜像。例如 839647521 的递减进制 中介数就是 12224376。 （此中介数加上 100 的递减进制数
13、 131 后得到新中介数 12224527） 还原方法：还原方法：递减进位制中介数的还原方法也刚好和递增进位制中介数相反。 递增进位制还原方法 是按照从中介数最高位（左侧）到最低位（右侧）的顺序来填数。而递减仅位置还原方法则从中 介数的最低位向最高位进行依次计数填空。例如对于新中介数 12224527，我给出了详细的还 原步骤。红色代表当前正在填充的空格。最终得到新排列 397645821。 新中介数新中介数 当前位当前位 新排列数新排列数 备注备注 初始 7 9 从右向左数 7 个空格， 第 8 个空格里填 “9” 2 9 8 从右向左数 2 个空格， 第 3 个空格里填 “8” 5 9 7
14、 8 从右向左数 5 个空格， 第 6 个空格里填 “7” 4 9 7 6 8 从右向左数 4 个空格， 第 5 个空格里填 “6” 2 9 7 6 5 8 从右向左数 2 个空格， 第 3 个空格里填 “5” 2 9 7 6 4 5 8 从右向左数 2 个空格， 第 3 个空格里填 “4” 2 3 9 7 6 4 5 8 从右向左数 2 个空格， 第 3 个空格里填 “3” 1 3 9 7 6 4 5 8 2 从右向左数 1 个空格， 第 2 个空格里填 “2” 最后补位 3 9 7 6 4 5 8 2 1 余下的空格填“1” 循环左移排列生成算法 映射方法：映射方法：循环左移排列生成算法与
15、递减进位排列生成算法非常相似，同样是在原始排列中找到 比当前数字小的数字个数。 只不过循环左移使用的是左循环搜索法， 而不是递减进位法使用的右 侧搜索。 所谓左循环搜索法是指从起始数字开始向左搜索， 如果到了左边界还没有发现终止数字， 则从右边界开始继续寻找，直到终止数字被发现。图中展示了 839647521 种以开始数字为 6， 结束数字为 5 和开始数字为 7，结束数字为 6 的左循环搜索区间，注意开始和结束数字是不包 括在区间内的。 具体到循环左移的排列生成法得映射方法，就是要为每一个数字确定这样一个区间。方法是以从 9 到 2 的顺序依次产生中介数中的数字，中介数从右向左产生（即原排列
16、的 9 产生的数字放到 中介数右数第一位，8 产生的数字放到中介数右数第二位，以此类推。这样才能得到递减进位制 数）。对于 9，产生的中介数字依然是 9 的右边比 9 小的数字的个数。但是从 8 开始一直到 2 中的每一个数 i，都是要做一个以 i+1 为开始数字，i为结束数字的左循环区间，并看这个左循 环区间中比 i小的数字的个数。例如对于排列 839647521，9 的右侧比 9 小的数字有 6 个；9 到 8 的左循环区间比 8 小的数字有 1 个；8 到 7 的左循环区间比 7 小的数字有 3 个；7 到 6 的 左循环区间比 6 小的数字有 1 个（如上面图下半部所示）；6 到 5 的左循环区间比 5 小的右 3 个数字（
