组合数学全排列生成算法组合数学中的全排列深成算法历来是组合数学考试的重要考察点，因此在这里我简单的介绍一下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个。

得到递增进制中介数72642321。

（此中介数加上100的递增进进制数4020后得到新中介数72652011）还原方法：还原方法为映射方法的逆过程。

你可以先写出辅助数字1 2 3 4 5 6 7 8 9，以及9个空位用于填充新排列。

然后从新中介数的最高位数起。

例如新中介数最高位是x，你就可以从辅助数字的第一个没有被使用的数字开始数起，数到x。

第x+1个数字就应当是空位的第一个数字。

我们将此数字标为“已用”，然后用其填充左起第一个空位。

然后，再看新中介数的次高位y，从辅助数字的第一个未用数字数起，数到一。

第y+1个数字就是下一个空位的数字。

我们将此数字标为“已用”，然后用其填充左起第二个空位。

依此类推，直到最后一个中介数中的数字被数完为止。

例如对于新中介数72652011，我们给出其辅助数字和空位的每一步的情况。

其中红色的数字代表“正在标记为已用”，“已用”的数字不会再被算在之后的计数当中。

当新中介数中所有的数字都被数完了，辅助数字中剩下的唯一数字将被填入最后的空位中。

最终得到新排列839741562。

递增进位排列生成算法映射方法：将原排列按照从9到2的顺序，依次查看其右侧比其小的数字的个数。

这个个数就是中介数的一位。

例如对于原排列839647521。

9的右侧比9小的数字有6个，8的右侧比8小的数字有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为例，我给出了详细的恢复步骤。

其中红色数字代表新填上的数字。

最后得到新排列869427351。

递减进位排列生成算法映射方法：递减进位制的映射方法刚好和递增进位制相反，即按照从9到2的顺序，依次查看其右侧比其小数字的个数。

但是，生成中介数的顺序不再是从左向右，而是从右向左。

生成的递减进制中介数刚好是递增进位排列生成算法得到中介数的镜像。

例如839647521的递减进制中介数就是12224376。

（此中介数加上100的递减进制数131后得到新中介数12224527）还原方法：递减进位制中介数的还原方法也刚好和递增进位制中介数相反。

递增进位制还原方法是按照从中介数最高位（左侧）到最低位（右侧）的顺序来填数。

而递减仅位置还原方法则从中介数的最低位向最高位进行依次计数填空。

例如对于新中介数12224527，我给出了详细的还原步骤。

红色代表当前正在填充的空格。

最终得到新排列397645821。

循环左移排列生成算法映射方法：循环左移排列生成算法与递减进位排列生成算法非常相似，同样是在原始排列中找到比当前数字小的数字个数。

只不过循环左移使用的是左循环搜索法，而不是递减进位法使用的右侧搜索。

所谓左循环搜索法是指从起始数字开始向左搜索，如果到了左边界还没有发现终止数字，则从右边界开始继续寻找，直到终止数字被发现。

图中展示了839647521种以开始数字为6，结束数字为5和开始数字为7，结束数字为6的左循环搜索区间，注意开始和结束数字是不包括在区间内的。

具体到循环左移的排列生成法得映射方法，就是要为每一个数字确定这样一个区间。

方法是以从9到2的顺序依次产生中介数中的数字，中介数从右向左产生（即原排列的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个数字（如上图上半部分所示）；……；3到2的左循环区间里比2小的数字有1个。

所以得到递减中介数10031316（此中结束加上100的递减进制数131得新中介数10031447）还原方法：循环左移的还原方法很自然。

首先画9个空格。

当拿到新的中介数后，从中介数的最右边向左边开始计数逐个计数。

计数的方法是，对于中介数最右边的数x9，从空格的最右端起数x9个空格，在第x9+1个空格上填上9。

然后对于中介数的每一位x i，沿着左循环的方向数x i个未占用空格，在第x i+1个空格里填上i，即可完成还原。

我给出了将中介数10031447还原的步骤，其中底纹代表为了定位下一个数字而数过的空格。

红色代表被填充的空格。

最终得到结果592138647。

邻位对换排列生成算法邻位对换法对连续生成排列作了优化，即通过保存数字的“方向性”来快速得到下一个排列。

然而当任意给定一个排列数，想恢复每个数字的方向性相对比较麻烦。

邻位对换法的关键就在于方向性。

映射方法：我们需要确定每一个数字的方向性，从2开始。

同时，设定b2b3b4b5b6b7b8b9为我们要求的中介数。

2的方向一定是向左（关于向左原因的讨论这里省略）。

b2就是从2开始,背向2的方向直到排列的边界比2小的数字。

知道了b2的值之后就可以依次推导出b3b4……直到b9的值，规则如下：对于每一个大于2的数字i，如果i为奇数，其方向性决定于b i-1的奇偶性，奇向右、偶向左。

如果i为偶数，其方向性决定于b i-1+b i-2的奇偶性，同样是奇向右、偶向左。

当得到方向性后，b i的值就是背向i的方向直到排列边界这个区间里比i小的数字的个数。

如此就能得到邻位对换法的中间数。

例如对于排列839647521:2的方向向左，背向2的方向中比2小的数字有1个，b2=13的方向由b2为奇可以断定向右，背向3的方向中比3小的数字有0个，b3=04的方向由b2+b3为奇可以断定向右，背向4的方向中比4小的数字有1个，b4=15的方向由b4为奇可以断定向右，背向5的方向中比5小的数字有2个，b5=26的方向由b4+b5为奇可以断定向右，背向6的方向中比6小的数字有1个，b6=17的方向由b6为奇可以断定向右，背向7的方向中比7小的数字有3个，b7=38的方向由b6+b7为偶可以断定向左，背向8的方向中比8小的数字有7个，b8=79的方向由b8为奇可以断定向右，背向9的方向中比9小的数字有2个，b9=2最终得到中介数10121372（此中介数加上100的递减数131后得到新的中介数10121523）还原方法：还原方法完全为映射方法的逆过程。