全排列的各种实现

1、用C+写一个函数，女口Foo(constchar*str),打印出str的全排列，如abc的全排列：abc,acb,bca,dac,cab,cba一全排列的递归实现为方便起见，用123来示例下。123的全排列有123、132、213、231、312、321这六种。首先考虑213和321这二个数是如何得出的。显然这二个都是123中的1与后面两数交换得到的。然后可以将123的第二个数和每三个数交换得到132。同理可以根据213和321来得231和312。因此可以知道全排列就是从第一个数字起每个数分别与它后面的数字交换。找到这个规律后，递归的代码就很容易写出来了：cppviewplaincopypr

2、int?/全排列的递归实现#include#includevoidSwap(char*a,char*b)TOC o 1-5 h zchart=*a;*a=*b;*b=t;/k表示当前选取到第几个数,m表示共有多少数.voidAllRange(char*pszStr,intk,intm)if(k=m)staticints_i=1;printf(第%3d个排列t%sn,s_i+,pszStr);TOC o 1-5 h zelsefor(inti=k;i=m;i+)/第i个数分别与它后面的数字交换就能得到新的排列Swap(pszStr+k,pszStr+i);AllRange(pszStr,k+1,

3、m);Swap(pszStr+k,pszStr+i);voidFoo(char*pszStr)AllRange(pszStr,0,strlen(pszStr)-1);intmain()printf(全排列的递归实现n);printf(-byMoreWindows( HYPERLINK /MoreWindows /MoreWindows)-nn);charszTextStr=123;printf(%s的全排列如下:n,szTextStr);Foo(szTextStr);return0;运行结果如下：全排列的递归实现-byMorlilindouis(http:/blog.csdn.nt/Morek

4、lindowsJ-inue全排列的递归实现-byMorelilindouisC HYPERLINK /MoreWindows /MoreWindows)注意这样的方法没有考虑到重复数字，如122将会输出:otarFafp斗parrafp別列鬲別狽列e.二二二.J二二剤科刊剂科科个个个个个个ny123456a123132213231321312contJ-ITrJFrTTrJJ-mEJAplrJJ-TTrJITTrJO下tr-r.MJMJ-H-MJ-y女歹歹歹歹歹歹eh二“J二二“二二“-二一123456a122122212221221212continue这种输出绝对不符合要求，因此现在要想办

5、法来去掉重复的数列。二去掉重复的全排列的递归实现由于全排列就是从第一个数字起每个数分别与它后面的数字交换。我们先尝试加个这样的判断一一如果一个数与后面的数字相同那么这二个数就不交换了。如122,第一个数与后面交换得212、221。然后122中第二数就不用与第三个数交换了，但对212，它第二个数与第三个数是不相同的，交换之后得到221o与由122中第一个数与第三个数交换所得的221重复了。所以这个方法不行。换种思维，对122,第一个数1与第二个数2交换得到212,然后考虑第一个数1与第三个数2交换，此时由于第三个数等于第二个数，所以第一个数不再与第三个数交换。再考虑212，它的第二个数与第三个数

6、交换可以得到解决221。此时全排列生成完毕。这样我们也得到了在全排列中去掉重复的规则一一去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换。用编程的话描述就是第i个数与第j个数交换时，要求i,j)中没有与第j个数相等的数。下面给出完整代码：cppviewplaincopyprint?/去重全排列的递归实现#include#includevoidSwap(char*a,char*b)TOC o 1-5 h zchart=*a;*a=*b;*b=t;/在pszStr数组中，nBegin,nEnd)中是否有数字与下标为nEnd的数字相等boolIsSwap(char*pszStr,

7、intnBegin,intnEnd)for(inti=nBegin;inEnd;i+)if(pszStri=pszStrnEnd)returnfalse;returntrue;TOC o 1-5 h z/k表示当前选取到第几个数表示共有多少数.voidAllRange(char*pszStr,intk,intm)if(k=m)staticints_i=1;printf(第%3d个排列t%sn,s_i+,pszStr);elsefor(inti=k;i=m;i+)/第i个数分别与它后面的数字交换就能得到新的排列if(IsSwap(pszStr,k,i)Swap(pszStr+k,pszStr+i

8、);AllRange(pszStr,k+1,m);Swap(pszStr+k,pszStr+i);voidFoo(char*pszStr)AllRange(pszStr,0,strlen(pszStr)-1);intmain()printf(去重全排列的递归实现n);printf(-byMoreWindows( HYPERLINK /MoreWindows /MoreWindows)-nn);charszTextStr=122;printf(%s的全排列如下:n,szTextStr);Foo(szTextStr);return0;51.运行结果如下:去重全排列的递归实现-byMoreldind

9、ows(http：/Morelilindouis)-122的全排列如下：第1个赫刘122第2个捋列212第M个排列221PressanykeytocontinueOK,到现在我们已经能熟练写出递归的方法了，并且考虑了字符串中的重复数据可能引发的重复数列问题。那么如何使用非递归的方法来得到全排列了？三全排列的非递归实现要考虑全排列的非递归实现，先来考虑如何计算字符串的下一个排列。如1234的下一个排列就是1243。只要对字符串反复求出下一个排列,全排列的也就迎刃而解了。如何计算字符串的下一个排列了？来考虑926520这个字符串，我们从后向前找第一双相邻的递增数字，20、52都是非递增的，26即满

10、足要求，称前一个数字2为替换数，替换数的下标称为替换点，再从后面找一个比替换数大的最小数（这个数必然存在），0、2都不行，5可以，将5和2交换得到956220,然后再将替换点后的字符串6220颠倒即得到9502260对于像4321这种已经是最“大”的排列，采用STL中的处理方法，将字符串整个颠倒得到最“小”的排列1234并返回false。这样，只要一个循环再加上计算字符串下一个排列的函数就可以轻松的实现非递归的全排列算法。按上面思路并参考STL中的实现源码，不难写成一份质量较高的代码。值得注意的是在循环前要对字符串排序下,可以自己写快速排序的代码(请参阅白话经典算法之六快速排序快速搞定)，也可

11、以直接使用VC库中的快速排序函数(请参阅使用VC库函数中的快速排序函数)。下面列出完整代码：cppviewplaincopyprint?/全排列的非递归实现#include#include#includevoidSwap(char*a,char*b)TOC o 1-5 h zchart=*a;*a=*b;*b=t;/反转区间voidReverse(char*a,char*b)while(ab)Swap(a+,b-);/下一个排列boolNext_permutation(chara)char*pEnd=a+strlen(a);if(a=pEnd)returnfalse;char*p,*q,*pF

12、ind;pEnd-;p=pEnd;while(p!=a)TOC o 1-5 h zq=p;-p;if(*p*q)/找降序的相邻2数，前一个数即替换数/从后向前找比替换点大的第一个数pFind=pEnd;while(*pFind=*p)-pFind;/替换Swap(pFind,p);/替换点后的数全部反转Reverse(q,pEnd);returntrue;TOC o 1-5 h zReverse(p,pEnd);/如果没有下一个排列，全部反转后返回truereturnfalse;intQsortCmp(constvoid*pa,constvoid*pb)return*(char*)pa-*(c

13、har*)pb;intmain()printf(全排列的非递归实现n);printf(-byMoreWindows( HYPERLINK /MoreWindows /MoreWindows)-nn);charszTextStr=abc;printf(%s的全排列如下:n,szTextStr);/加上排序qsort(szTextStr,strlen(szTextStr),sizeof(szTextStr0),QsortCmp);inti=1;doprintf(第34个排列t%sn,i+,szTextStr);while(Next_permutation(szTextStr);return0;测试

14、一下，结果如下所示:全排列的非递归实现-byMorlilindouis(/MoreldindouiG日be的全韦卡歹L如下：第1个壬abc第2个兀acb篦3个产bac為耳个用歹1bca第5个之阳Lcab第6个排歹LcbaPressanyktocontinue.将字符串改成cba*会输出:全排列的非递归实现-byMorlilindouis( HYPERLINK /Horeklindows /Horeklindows)inueabcacbbacbcacabcbacont下如列列列列列列列全个个个个个个a-123456S邯Saeb穹Frlrrf弓rlmarjr-vllr厂c+s*s+s山倂+.s*.p至此我们已经运用了递归与非递归的方法解决了全排列问题，总结一下就是：全排列就是从第一个数字起每个数分别与它后面的数字交换。去重的全排列