全排列遞歸演算法
思路:先有一個起始排列，如1234.從後面掃描，直到找到a[k],a[k]<a[k+1];再從後面掃描，直到找到a[j],這里有 a[k]<a[j]。交換a[k],a[j].再把a[k+1],...a[n-1]排序（從小到大），即得到了一個排列，再循環下去，直到找出所有的排序。用C語言的，參考下: http://user.qzone.qq.com/646203846/infocenter?ptlang=2052
B. 遞歸的全排列產生演算法
我說說我對這段程序的大致理解過程。水平有限，難免紕漏。
咋一看我也理解不了，只是知道了函數第二個參數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到首位置的情況。這個結論是我又用了一次數學歸納法的思考方式才得出的。
C. 全排列 遞歸演算法 NOIP題目
不要急於看代碼，你心理要知道全排列的思路，不注重思路是很多程序員易犯的錯誤。
全排列演算法：
如果我求得固定第一位後的排列，那麼全部排列就可以求出，固定第一位有10種可能，可以循環求得。
如果我求得固定第二位後的排列，固定第一位後的排列就可以求出，固定第二位有9種可能，可以循環求得。
。。。
如果我求得固定第10位後的排列，固定第9位後的排列就可以求出，固定第10位有1種可能，可以循環求得。
這很明顯是遞歸的演算法。
設perm(int k)為全部排列的集合，k為數字的位置
perm(int k){
for(j=k;j<=n;j++) //循環數組，確定k位的數值
{
t=a[k];a[k]=a[j];a[j]=t;/* 交換a［k］和a［j］的位置，目的是為了確定k位的數值*/
______③perm(k+1)______;//求得確定k位後的全部序列
t=a[k];______④a[k]=a[j]; a[j]=t______;/* 交換a［k］和a［j］的位置*/
}
}
D. 關於全排列遞歸演算法
這個演算法，是把每一個數與末尾的數逐一交換，
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個數；
E. 全排列遞歸演算法的時間復雜度怎麼算
復雜度就是排列組合總數：n!
F. 哪位高手能幫我參透全排列的遞歸演算法，跪謝~~
知道漢諾塔的遞歸程序的意思嗎
就是先控制一個不動，讓剩餘的排列好，然後再移動第一個，再排列好剩餘的
這個程序也是這個意思
舉個例子說 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
G. 全排列or遞歸 演算法題，求一個最優演算法
這題並不是全排列，如果全排列是O(n!*n)的復雜度，完全無法接受，正解是概率期望DP
#include<stdio.h>
doubledp[1001];
intmain()
{
dp[0]=0;//0個人當然是0
inti;
doublesum=0;//記錄前面所有dp的和
for(i=1;i<=1000;i++)
{
dp[i]=sum/i+1;
sum+=dp[i];
}
while(~scanf("%d",&i))
printf("%.2lf
",dp[i]);
}
H. C語言 求此全排列遞歸演算法解析
used數組是全局變數有隱含初值0；
關於全排列的演算法你可以理解為深搜加回溯。
#include<stdio.h>
#define
MAX
10
int
used[MAX];
//用來標記數字是否已經在前面使用過
int
result[MAX];
//存放結果
int
N;
void
print()
//輸出結果
{
int
i;
for(i=0;i<N;i++)
printf("%d
",result[i]);
printf("\n");
}
void
proc(int
step)
//step用來記錄已經擺好了幾個數
{
int
i;
if(step==N)
//如果已經擺好了N個數，那麼結果就產生了，就輸出結果
print();
else
{
for(i=0;i<N;i++)
//枚舉1-N，找到沒有使用過的最小的數
{
if(!used[i])
//沒有使用過
{
used[i]=1;
//標記i已經使用
result[step]=i+1;
//記錄結果
proc(step+1);
//遞歸求解
used[i]=0;
//這里就是所謂的回溯，也許比較難理解，你可以人工走一遍加深理解。其實回溯的主要想法是"還原現場".當執行到這一步時，i+1
這個數放在第step個位置的情況已經解決了，我們就要拿出i+1這個數，把它標記為未使用。
}
}
}
}
int
main()
{
scanf("%d",&N);
proc(0);
return
0;
}
I. 全排列的遞歸
設(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);}}}}
J. 全排列遞歸演算法P(m,n)
#include<stdio.h>
main()
{
int i,j,k,m;
for(i='A';i<='G';i++)
for(j='A';j<='G';j++)
for(k='A';k<='G';k++)
for(m='A';m<='G';m++)
printf("%c%c%c%c",i,j,k,m);
}
注意這里在輸出的時候沒有使用printf("%c%c%c%c\n",i,j,k,m)換行符，是因為輸出的數據太多，會顯示不下