全排列算法原理与实现53823

《全排列算法原理与实现53823》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、全排列算法原理和实现53823http://acm-hit.sunner.cn/index.php全排列是将一组数按一定顺序进行排列，如果这组数有n个，那么全排列数为n!个。现以{1,2,3,4,5}为例说明如何编写全排列的递归算法。1、首先看最后两个数4,5。它们的全排列为45和54,即以4开头的5的全排列和以5开头的4的全排列。由于一个数的全排列就是其本身，从而得到以上结果。2、再看后三个数3,4,5。它们的全排列为345、354、435、453、534、543六组数。即以3开头的和4,5的全排列的组合、以4开头的和3,5的全排列的组合和以5开头

2、的和3,4的全排列的组合.从而可以推断，设一组数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个数的全排列。算法如下：#includeintn=0;voidswap(int*a,int*b){intm;m=*a;*a=*b;*b=m;}voidperm(intlist[]

3、,intk,intm){inti;if(k>m){for(i=0;i<=m;i++)printf("%d",list[i]);printf("");n++;}else{for(i=k;i<=m;i++){swap(&list[k],&list[i]);perm(list,k+1,m);swap(&list[k],&list[i]);}}}intmain(){intlist[]={1,2,3,4,5};perm(list,0,4);printf("total:%d",n);return0;}谁有更高效的递归和非递归算法，请回贴。《银河系列原创教

4、程》发布000(请您对文章做出评价)postedon2008-05-1109:30银河使者阅读(5394)评论(9)编辑收藏网摘所属分类:algorithmBody:46.875,BeforeCate:0,62.5,Total:1265.625评论1546187#1楼2008-05-1110:25lucklier[未注册用户]递归的话如果排列的数字多了，效率可能会比较低，高中的时候为了奥赛这个问题研究了比较长时间，用pascal写过一个，不过现在都忘了。有时间俺也去研究研究回复引用#2楼2008-05-1123:32镜涛递归深度对性能的影响会很大，呵

5、呵。对算法研究不深就不献丑啦回复引用查看#3楼2008-06-0419:56ptrlink[未注册用户]为什么总有少数组数会出现错位呢？回复引用#4楼2008-07-0815:48asfasfas[未注册用户]如果数组中有重复的数，输出会重复，怎么解决？回复引用#5楼2008-10-0515:23五行连环[未注册用户]if(k>m)应该是if(k==m)回复引用#6楼2008-11-2813:24miao44[未注册用户]优化了一下intperm(intlist[],intk,intm){inti;staticintn;...swap(list[k]

6、,list[i]);...swap(list[k],list[i]);...returnn;}main(){intlist[5]={1,2,3,4,5};printf("total:%d",perm(list,0,4));}这样就可以不用定义全局变量n,更友好。另外swap函数可以不用重写，直接使用系统函数，去掉前面的取址符就可以了。回复引用#7楼2009-03-1414:35YJC[未注册用户]5楼的你才错了不是等号是大于号因为这里多一层回复引用#8楼2009-04-2716:57FC[未注册用户]思想就是你说的这样,代码好像更好了点,献丑#i

7、ncludevoidswap(char*a,char*b){chart;t=*a;*a=*b;*b=t;}voidprint(char*a,intl){inti=0;for(;i

8、chara[4]={'a','b','c','d'};permut(a,0,3,4);return0;}回复