使用C++实现全排列算法的方法详解
本文导语: 代码如下:不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。其中中介数依据算法的不同会的到递增进位制数和递减进位制数。关于排列和中介数的一一对应性的证明我们...
不论是哪种全排列生成算法,都遵循着“原排列”→“原中介数”→“新中介数”→“新排列”的过程。
其中中介数依据算法的不同会的到递增进位制数和递减进位制数。
关于排列和中介数的一一对应性的证明我们不做讨论,这里仅仅给出了排列和中介数的详细映射方法。
· 递增进位制和递减进位制数
所谓递增进位制和递减进位制数字是指数字的进制随着数字位置的不同递增或递减。通常我们见到的都是固定进制数字,如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个排列为例。
· 递增进位排列生成算法映射方法:将原排列按照从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。
void next_Permutations_by_increDecimal(int dataArr[],int size){
int i;
int *resultArr = new int[size];
int index = 0;
map::iterator iter;
//第一步 求出中介数
//由大到小,得到并记录当前排列中,数字i的右边比其小的数的个数
map agentMap;
for(i=0; i