全排列是算法學習的一個初級問題，也是近幾年IT公司比較熱衷的問題。最近因為一個朋友的實際問題用到了類似全排列的算法，所以把相關的代碼總結一下。
一、問題描述
全排列的問題非常簡單，比如給定三個數字1、2、3，請將三個數字的所有排列組合按大小順序給出。這樣我們期待的結果就是：123，132，213，231，312，321
二、第一種遞歸算法分析
對於給定的n個數字，顯然有n！種排列方式。關鍵在於怎樣將所有的排列得到，一種顯然的方式是首先選出第一位上的數字，然後回溯選擇第二位上的數字，然後是第三位……只需要確保每一位上選擇的數字不重復就可以了。這種算法比較好理解，遞歸也比較好設計，先上代碼（c++）：
1 #include<iostream>
2 #include<fstream>
3 using namespace std;
4
5 ifstream fin;
6 ofstream fout;
7 int flags[100];
8 int numbers[100];
9 int n;
10
11 void search(int loc){
12 if(loc==n){
13 fout<<numbers[0]+1;
14 for(int i=1;i!=n;i++)
15 fout<<","<<numbers[i]+1;
16 fout<<endl;
17 }else{
18 for(int i=0;i!=n;i++)
19 if(flags[i]){
20 flags[i]=0;
21 numbers[loc]=i;
22 search(loc+1);
23 flags[i]=1;
24 }
25 }
26 }
27
28 int main(){
29
30 //fin.open("input.txt",ios::in);
31 fout.open("QPL.txt",ios::out);
32
33 cin>>n;
34 for(int i=0;i!=n;i++)
35 flags[i]=1;
36 search(0);
37 }
算法的關鍵就是search函數的實現。首先是退出條件的確定，search函數從左到右每個坑裡填一個數字，當loc==n的時候填完所有的坑，這樣一個排列便完成了。然後是往每個坑裡填數字的過程，就是那個for循環，對於每個坑數字從0到n填，同時判定沒有重復使用。
這種實現的好處是比較直觀，可拓展性比較強。大家可以試一下修改邊界條件的判定標准會有什麼效果。
三、第二種遞歸算法分析
網上還有這樣一種看似簡潔的遞歸算法。算法通過觀察全排列的產生方式，以123為例，他的全排列為123，132，213，231，312，321.通過觀察可以發現，123的全排列就是1+（23的全排列）加上2+（13的全排列）加上3+（12的全排列）這裡的遞歸的設計就是1+perm（23）然後交換1和2再執行2+perm（13）然後交換2和3執行3+perm（23）。
代碼設計如下：
1 #include <iostream>
2 #include <fstream>
3 #include <stdlib.h>
4
5 using namespace std;
6
7 void swap(char *a,char *b)
8 {
9 char temp;
10 temp=*a;
11 *a=*b;
12 *b=temp;
13 }
14
15 void Perm(char *pszStr, int k, int m)
16 {
17 if (k == m)
18 {
19 static int s_i = 1;
20 cout<<"the "<<s_i ++<<" line"<<pszStr<<endl;
21 }
22 else
23 {
24 for (int i = k; i <= m; i++) //第i個數分別與它後面的數字交換就能得到新的排列
25 {
26 swap(pszStr + k, pszStr + i);
27 Perm(pszStr, k + 1, m);
28 swap(pszStr + k, pszStr + i);//恢復現場
29 }
30 }
31 }
32
33 int main(int argc, const char * argv[])
34 {
35 char str[]="1234";
36 Perm(str,0, 3);
37 return 0;
38 }
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;
}
知道漢諾塔的遞歸程序的意思嗎
就是先控制一個不動，讓剩余的排列好，然後再移動第一個，再排列好剩余的
這個程序也是這個意思
舉個例子說 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("......余下全文>>
