全排列遞歸演算法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裡面有一個漢諾塔,就是非用遞歸才能解決的一個問題!可以仔細理解一下哦!