全排列递归算法java

1. 全排列的递归

设(ri)perm(X)表示每一个全排列前加上前缀ri得到的排列.当n=1时,perm(R)=(r) 其中r是唯一的元素,这个就是出口条件.
当n>1时,perm(R)由(r1)perm(R1),(r2)perm(R2),...(rn)perm(Rn)构成. voidPerm(list[],intk,intm)//k表示前缀的位置,m是要排列的数目.{if(k==m-1)//前缀是最后一个位置,此时打印排列数.{for(inti=0;i<m;i++){printf(%d,list[i]);}printf( );}else{for(inti=k;i<m;i++){//交换前缀,使之产生下一个前缀.Swap(list[k],list[i]);Perm(list,k+1,m);//将前缀换回来,继续做上一个的前缀排列.Swap(list[k],list[i]);}}}//此处为引用,交换函数.函数调用多,故定义为内联函数.inlinevoidSwap(int&a,int&b){inttemp=a;a=b;b=temp;}函数Perm(int list[],int k,int m)是求将list的第0~k-1个元素作为前缀、第k~m个元素进行全排列得到的全排列，如果k为0，且m为n，就可以求得一个数组中所有元素的全排列。
其想法是将第k个元素与后面的每个元素进行交换，求出其全排列。这种算法比较节省空间。 n个数的排列可以从1.2....n开始,至n.n-1....2.1结束。
也就是按数值大小递增的顺序找出每一个排列。
以6个数的排列为例，其初始排列为123456,最后一个排列是654321,如果当前排列是124653,找它的下一个排列的方法是，从这个序列中从右至左找第一个左邻小于右邻的数，如果找不到，则所有排列求解完成，如果找得到则说明排列未完成。
本例中将找到46,计4所在的位置为i,找到后不能直接将46位置互换，而又要从右到左到第一个比4大的数，本例找到的数是5，其位置计为j，将i与j所在元素交换125643,然后将i+1至最后一个元素从小到大排序得到125346，这就是124653的下一个排列，如此下去，直至654321为止。算法结束。 intb[N];intis_train(inta[],intn){inti,j,k=1;for(i=1;i<=n;i++){for(j=i+1;j<=n;j++)if(a[j]<a[i])b[k++]=a[j];/*判断是否降序*/if(k>1)is_train(b,k);elsereturn(1);}}voidtrain(inta[],intn){inti,j,t,temp,count=1;t=1;printf(inputthe%3dthway:,count);for(i=1;i<=n;i++)printf(%3d,a[i]);printf( );while(t){i=n;j=i-1;/*从右往左找,找第一个左邻比右邻小的位置*/while(j&&a[j]>a[i]){j--;i--;}if(j==0)t=0;elset=1;if(t){i=n;/*从右往左找,找第一个比front大的位置*/while(a[j]>a[i])i--;temp=a[j],a[j]=a[i],a[i]=temp;quicksort(a,j+1,N);/*调用快速排序*//*判断是否符合调度要求*/if(is_train(a,N)==1){count++;printf(inputthe%3dthway:,count);for(i=1;i<=n;i++)printf(%3d,a[i]);printf(n);}}}}

2. 递归的全排列产生算法

我说说我对这段程序的大致理解过程。水平有限，难免纰漏。

咋一看我也理解不了，只是知道了函数第二个参数i表示首元素，第三个参数n表示尾元素。于是我开始按照数学归纳法的方式来理解（我一直觉得递归算法要按照数学归纳法的方式才好理解）。
我印象中数学归纳法的要点好像是包括如下2点：
1.初始的几种情况，即n=0，n=1的情况；
2.第k次与第k-1次间的关系，即已知第k-1次的结果，如何求出第k次的结果。

放到这个问题中：
1.通过考虑n=0，n=1等的几种情况，我大概知道了这个函数的最终结果是打印出一组全排列。不过有些实现细节还没完全明白。
2.已知k-1个元素的全排列，如何求出k个元素的全排列？结合perm函数中的递归调用是把第二个参数加1，我就想出这个问题的答案了：首先确定首元素的值，这样，需要全排列的元素就少了1个，递归也就成立了。

想到这里应该就差不多了，整个算法的思路是：
从元素0开始依次确定各个元素的值，当确定了最后一个元素的值时，就打印整个数组。

最后回答下你的问题：
1.if语句就是当确定了最后一个元素的值后的处理；
2.两个swap实现的就是确定首元素的算法。
另外这里要用两个swap是为了保证全排列后各元素顺序不会乱，否则会出现将相同的元素swap到首位置的情况。这个结论是我又用了一次数学归纳法的思考方式才得出的。

3. 什么情况下要用到递归算法C语言中的

在一个子程序（过程或函数）的定义中又直接或间接地调用该子程序本身，称为递归。
递归是一种非常有用的程序设计方法。用递归算法编写的程序结构清晰，具有很好的可读性。
递归算法的基本思想是：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
利用递归算法解题，首先要对问题的以下三个方面进行分析：
把这些步骤或等式确定下来。 把以上三个方面分析好之后，就可以在子程序中定义递归调用。记得C里面有一个汉诺塔,就是非用递归才能解决的一个问题!可以仔细理解一下哦!