全排列代码

题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。分析：此题最初整理于去年的微软面试100题中第53题，第二次整理于微软、Google等公司非常好的面试题及解答[第61-70题]第67题。无独有偶，这个问题今年又出现于今年的2011.10.09百度笔试题中。ok，接下来，咱们先好好分析这个问题。一、递归实现从集合中依次选出每一个元素，作为排列的第一个元素，然后对剩余的元素进行全排列，如此递归处理，从而得到所有元素的全排列。以对字符串abc进行全排列为例，我们可以这么做：以abc为例固定a，求后面bc的排列：abc，acb，求好后，a和b交换，得到bac固定b，求后面ac的排列：bac，bca，求好后，c放到第一位置，得到cba固定c，求后面ba的排列：cba，cab。代码可如下编写所示[cpp]#includeiostreamusingnamespacestd;voidPermutation(char*pStr,char*pBegin);voidpermutation(char*pStr){Permutation(pStr,pStr);}voidPermutation(char*pStr,char*pBegin){if(!pStr||!pBegin)return;if(*pBegin=='\0'){printf(%s\n,pStr);}else{for(char*pCh=pBegin;*pCh!='\0';++pCh){//swappChandpBeginchartemp=*pCh;*pCh=*pBegin;*pBegin=temp;Permutation(pStr,pBegin+1);//restorepChandpBegintemp=*pCh;*pCh=*pBegin;*pBegin=temp;}}}intmain(){charstr[]={'a','b','c','d','\0'};permutation(str);getchar();return0;}给定一个字符串，其含有的字符各不相同。程序输出该字符串的所有排列（全排列）情形。完善代码只填一个语句voidf(char*str,intlen,intn){inti;chartmp;char*p=(char*)malloc(__________);if(n==len-1){printf(%s\n,str);}else{for(i=n;ilen;i++){strcpy(p,str);tmp=*(str+n);*(str+n)=*(str+i);*(str+i)=tmp;_______________;strcpy(str,p);}}free(p);}intmain(intargc,char**argv){charstr[]=xyz;f(str,3,0);printf(\n);return0;}例如：给定字符串“xyz”，则程序输出：xyzxzyyxzyzxzyxzxy题目：输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。我们以三个字符abc为例来分析一下求字符串排列的过程。首先我们固定第一个字符a，求后面两个字符bc的排列。当两个字符bc的排列求好之后，我们把第一个字符a和后面的b交换，得到bac，接着我们固定第一个字符b，求后面两个字符ac的排列。现在是把c放到第一位置的时候了。记住前面我们已经把原先的第一个字符a和后面的b做了交换，为了保证这次c仍然是和原先处在第一位置的a交换，我们在拿c和第一个字符交换之前，先要把b和a交换回来。在交换b和a之后，再拿c和处在第一位置的a进行交换，得到cba。我们再次固定第一个字符c，求后面两个字符b、a的排列。既然我们已经知道怎么求三个字符的排列，那么固定第一个字符之后求后面两个字符的排列，就是典型的递归思路了。基于前面的分析，我们可以得到如下的参考代码，注意此算法有重复：voidPermutation(char*pStr,char*pBegin);///////////////////////////////////////////////////////////////////////////Getthepermutationofastring,//forexample,inputstringabc,itspermutationis//abcacbbacbcacbacab/////////////////////////////////////////////////////////////////////////voidmain(){chartest[]=abc;Permutation(test,test);}///////////////////////////////////////////////////////////////////////////Printthepermutationofastring,//Input:pStr-inputstring//pBegin-pointstothebegincharofstring//whichwewanttopermutateinthisrecursion/////////////////////////////////////////////////////////////////////////voidPermutation(char*pStr,char*pBegin){if(!pStr||!pBegin)return;//ifpBeginpointstotheendofstring,//thisroundofpermutationisfinished,//printthepermutedstringif(*pBegin=='\0'){printf(%s\n,pStr);}//otherwise,permutestringelse{for(char*pCh=pBegin;*pCh!='\0';++pCh){//swappChandpBeginchartemp=*pCh;*pCh=*pBegin;*pBegin=temp;Permutation(pStr,pBegin+1);//restorepChandpBegintemp=*pCh;*pCh=*pBegin;*pBegin=temp;}}}设计1个程序，给出1个字符串，就能输出这个字符串的全排列。例如，给出了ABC。就可以输出ABC,ACB,BCA,BAC,CAB,CBA.要求用递归的方法解决，现在已经有了以下程序：#includestdio.h#includestring.hmain(){charstr[20];staticvoidR(charstr[],intk);staticvoide(charstr[],intk,inti);scanf(%s,str);printf(\n);R(&str,0);}staticvoidR(charstr[],intk){inti;if(k==strlen(str))printf(%s\n,str);elsefor(i=k;istrlen(str);i++){e(str,k,i);R(str,k+1);e(str,k,i);}}staticvoide(charstr[],intp1,intp2){chartemp;temp=str[p1];str[p1]=str[p2];str[p2]=temp;}但是这个程序有1个问题。。如果字符串为AABB。那么他仍然会输出24个结果，而其中很多是重复的。实际结果中只需要AABB,ABAB,ABBA,BAAB,BABA,BBAA.请问怎么修改。或者怎么重新写1个来完善这个程序题目描述:输入一个字符串，打印出该字符串中字符的所有排列。例如输入字符串abc，则输出由字符a、b、c所能排列出来的所有字符串abc、acb、bac、bca、cab和cba。解析：递归法：首先看最后两个字符b,c。它们的全排列为bc和cb,即以b开头的c的全排列和以c开头的b的全排列。再看三个字符a，b，c。他们的全排列（a，b，c）、（a，c，b）、（b，a，c）、（b，c，a）、（c，a，b）、（c，b，a）从而可以推断，设一组数p={r1,r2,r3,...,rn},全排列为perm(p)，pn=p-{rn}。因此perm(p)=r1perm(p1),r2perm(p2),r3perm(p3),...,rnperm(pn)。当n=1时perm(p}=r1。为了更容易理解，将整组数中的所有的数分别与第一个数交换，这样就总是在处理后n-1个数的全排列。代码：(下面的输入以(a，b，c，d)为例)#includeiostreamusingnamespacestd;voidswap(char*x,char*y){inttemp;temp=*x;*x=*y;*y=temp;}voidperm(char*list,inti,intmax){if(imax){for(intj=0;j=max;j++){coutlist[j];}coutendl;}else{for(intj=i;j=max;j++){swap(&list[i],&list[j]);perm(list,i+1,max);swap(&list[i],&list[j]);}}}intmain(){charlist[4]={'a','b','c','d'};perm(list,0,3);return0;}如果用递归算法结果是1,2,31,3,22,1,32,3,13,2,13,1,2这是由于算法只是考虑到了如何输出全排列，而没有考虑到换位是否有问题。所以我提出了解决方案，就是换位函数修改下如123换位的话,不应该直接321这样,让3和1直接换位;而是让3排在最前后,12依次向后以下介绍全排列算法四种：(A)字典序法(B)递增进位制数法(C)递减进位制数法(D)邻位对换法(A)字典序法对给定的字符集中的字符规定了一个先后关系，在此基础上规定两个全排列的先后是从左到右逐个比较对应的字符的先后。[例]字符集{1,2,3},较小的数字较先,这样按字典序生成的全排列是:123,132,213,231,312,321。[注意]一个全排列可看做一个字符串，字符串可有前缀、后缀。1）生成给定全排列的下一个排列所谓一个的下一个就是这一个与下一个之间没有其他的。这就要求这一个与下一个有尽可能长的共同前缀，也即变化限制在尽可能短的后缀上。[例]839647521是1--9的排列。1—9的排列最前面的是123456789，最后面的是987654321，从右向左扫描若都是增的，就到了987654321，也就没有下一个了。否则找出第一次出现下降的位置。B递增进位制数法1)由排列求中介数在字典序法中，中介数的各位是由排列数的位决定的.中介数位的下标与排列的位的下标一致。在递增进位制数法中，中介数的各位是由排列中的数字决定的。即中介数中各位的下标与排列中的数字(2—n)一致。可看出n-1位的进位链。右端位逢2进1，右起第2位逢3进1，…，右起第i位逢i+1进1，i=1,2,…,n-1.这样的中介数我们称为递增进位制数。上面是由中介数求排列。由序号（十进制数）求中介数（递增进位制数）如下：m=m1,0≤m≤n!-1m1=2m2+kn-1,0≤kn-1≤1m2=3m3+kn-2,0≤kn-2≤2……………mn-2=(n-1)mn-1+k2,0≤k2≤n-2mn-1=k1,0≤k1≤n-1p1p2…pn←→(k1k2…kn-1)↑←→m在字典序法中由中介数求排列比较麻烦，我们可以通过另外定义递增进位制数加以改进。为方便起见，令ai+1=kn-1，i=1,2,…,n-