全排列的遞歸演算法
1. 哪位高手能幫我參透全排列的遞歸演算法，跪謝~~
知道漢諾塔的遞歸程序的意思嗎
就是先控制一個不動，讓剩餘的排列好，然後再移動第一個，再排列好剩餘的
這個程序也是這個意思
舉個例子說 1234
1。先保持1不動，排列234
2。保持2不動，排列34
3。保持3不動，排列4
4。得到4；輸出1234。
5。然後跳轉到3，將3與4互換，
6。得到3；輸出1243。
7。跳轉到2，將2與3互換，
8。重復3-6，得1324，1342。
9。跳轉到2，將2與4互換，得到1423，1432。
以下省略若干步。。
最後就得到全排列
解答完畢
一個比較好的全排列演算法(c語言) -|killniu 發表於 2006-4-18 23:39:00
我有一個比較好的全排列演算法，我驗證了3、4、5的結果是正確的。
程序中沒有使用遞歸，只是幾個循環，速度還令人滿意。
在C466A，Win2000的機器上，進行8個數字的全排列，結果不顯示，重定向到一個文本文件中，耗時不到一秒鍾
。9個數字的全排列耗時6秒種。10個數字的全排列55秒種。（以上都不顯示結果，均重定向到一個文本文件）
11個數字的全排列（不顯示結果，在原程序中不定義ISPRINT）耗時大約16秒鍾。
。
歡迎各位指點
演算法為：用兩個數組，一個數組存放當前結果，第二個數組是每一個數是否已經使用的標志。比如對10個數進
行全排列，第一個結果是：0 1 2 3 4 5 6 7 8 9。
然後把每一個數的使用標志均置為1。
然後開始主循環：
先列印當前的結果。
在前一個得到的結果中，從後往前找第一個由小到大排列的數。每找一次均置當前位上的數字的使用標志
為0，然後找第一個比這個數大但是沒有使用過的數。
比如前一個結果是：4 1 9 7 8 2 5 0 6 3，那麼從後往前第一個由小到大排列的數是0，第一個比0大但是沒有
使用過的數是3（因為比0大的數字里只有6和3）。最後由小到大依次列印剩餘沒有使用過的數字。所以下一個
結果是4 1 9 7 8 2 5 3 0 6。
源程序為（在BC++3.0下編譯成功）：
＃i nclude<stdio.h>/*這兩個庫函數是習慣性的加上去的^_^。*/
＃i nclude<stdlib.h>
#define ISPRINT/*是否列印結果的標志*/
#define MAX 200/*最大的數*/
unsigned int *_NUM;/*用於存放一條結果的數組指針*/
char *_NUMFLAG;/*用於存放是否已經使用的標志*/
#define NUM(j) (*(_NUM+(j)))/*第j位的數字*/
#define NUMFLAG(j) (*(_NUMFLAG+(j)))/*數字j是否已經使用的標志,0為沒有使用，1為已經使用*/
#define NUMUSE(j) (*(_NUMFLAG+(*(_NUM+(j)))))/*第j位上的數字是否已經使用的標志,0為沒有使用，1為已
經使用*/
void main()
{
unsigned int number,j;
int i;
printf(" Input number=");scanf("%u",&number);
if((number>=MAX)||(number<=1)){puts("輸入數據錯誤。");exit(-1);}
/*初始化內存和第一個結果*/
_NUM=(unsigned int*)malloc(sizeof(unsigned int)*number);
if(!_NUM){puts("分配給_NUM出現內存不足");exit(-1);}
_NUMFLAG=(char*)malloc(sizeof(char)*number);
if(!_NUMFLAG){puts("分配給_NUMFLAG出現內存不足");exit(-1);}
for(i=0;i<number;i++)NUM(i)=i,NUMFLAG(i)=1;/*初始化第一條結果和使用標志*/
do{/*主循環*/
#ifdef ISPRINT/*列印結果*/
for(j=0;j<number;j++)printf("%d ",NUM(j));/*列印一條結果。*/
puts("");/*並換行*/
#endif
NUMUSE(number-1)=0;//置最後一位數字的使用標志為0.
/*在前一個結果中從後往前尋找第一個從小到大排列的數，並存放到變數j中*/
for(i=number-2;i>=0;i--){
NUMUSE(i)=0;
if(NUM(i)<NUM(i+1))break;
}
if(i<0)break;/*從這里退出主循環.*/
for(j=NUM(i)+1;j<number;j++){
if(!NUMFLAG(j))break;
}
NUMFLAG(j)=1;
NUM(i)=j;
for(j=0,i++;i<number;j++)
if(!NUMFLAG(j))NUM(i++)=j,NUMFLAG(j)=1;
}while(1);
/*釋放內存*/
free(_NUM);
free(_NUMFLAG);
}
/*程序結束*/
當然了這個程序的速度並不是最快的，程序中還有很大的優化餘地，還可以減少一些循環，或者採用其他更好的演算法。
下載源程序http://263.csdn.net/FileBBS/files/2001_8/T_387_1.zip
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. 關於全排列遞歸演算法
這個演算法，是把每一個數與末尾的數逐一交換，
k>m 說明已交換完畢，就輸出了，這是遞歸的結束條件。
要學到一定的基本功才能明白。
---------------------------------------------------------------------------
我這個程序，我也編過，放在西祠C++BUILDER論壇里。
你先要掌握，排列的方法才能看懂這個程序。
在這知道里，也答過兩次。
為了增加可理解性，我略改了一下方法，我的方法
與你的方法遞歸方向不同。
http://www.xici.net/d190786398.htm
此演算法為遞歸法顯示排列數，沒發現比這更簡單、明了的遞
歸演算法。此演算法只要練智商的作用，沒有其它實用價值，階
乘級的佔用時間、空間，數一大，堆棧很快暴了。
演算法的要點：
1.列N個數的排列，可化為N個的N-1階排列：
最末一個數是 D[n-1]，把這個位置的N個數的可能性列出，
就是每一個數 與末尾逐一交換位置，就是N種情況，每一種
情況再求N-1的全排列，就是遞歸調用了；
交換位置後，就調用自已，但必須恢復剛才的交換，以便下一次
交換；
2.當階數遞歸到1時，就直接輸出這N個數；
4. 誰能解釋一下用遞歸做的排列演算法的詳細步驟參考王曉東的《計算機演算法設計與分析》p11
用到遞歸的排序演算法有快速排序和歸並排序。
快速排序：先選最開始的元素為樞軸，然後分別從兩頭中的一頭開始與樞軸比較。後面的應該大於樞軸，前面的應該小於樞軸，不然則交換（前面與後面），最後確定下來的位置（前後重合）就是樞軸的位置。這樣一來原序列就一分為二。不斷遞歸，再一分為二，最後直到被分為的兩端中有一個元素單獨的時候就結束分割。
歸並排序:第一次兩個兩個的來，排序之後就歸並成一個有序列，然後再四個四個的來，排序之後歸並成一個有序列……直到最後兩個歸並為一個有序列。
5. 遞歸全排列 c語言 看不懂
perm（list,i,j）是一個全排列函數，拿你上面的列子來說：
perm(list,0,5)意思是數組list的前6個數（第0個數到第5個數）的所有排列，它細分的話就等於：第0個數和第1個數互換以後的perm(list,1,5) 第0數和第2數互換perm(list,1,5) ....第0數和第5數互換的perm(list,1,5) 和它本身的所在0位置的perm(list, 1, 5)
如假如6個數是1 2 3 4 5 6
他們的排列就 * * * * * * perm(list,0,5)
1 * * * * * perm(list,1,5)
2 * * * * * perm(list,1,5)
3 * * * * * perm(list,1,5)
4 * * * * * perm(list,1,5)
5 * * * * * perm(list,1,5)
6 * * * * * perm(list,1,5) 就是每一個數都在第0個位置上面都出現一次以後的排列總和。 也就是它的for循環的意思
這只是形象的比喻一下