題目描述
非遞歸，按序輸出集合全排列，是在筆試面試中經常考的問題。遞歸輸出集合的全排列相對來說還是比較簡單的，而非遞歸實現這個問題需要一些小技巧。
全排列是將集合中的元素（可以為數字，可以為字符），按照字典序生成所有排列的集合，並輸出這些排列。以數字集合距離，集合{1,2,3}的按序全排列為：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
這樣3個元素一共生成了6個排列，即M個元素會生成M！個全排列序列。
非遞歸思路
遞歸的解題方法有時間另開一文敘述，這裡要介紹的是非遞歸的思路。還是同樣的以數字集合{1,2,3}為例。
這個集合生成的有序序列集合中的第一個序列是1 2 3，這個很容易能夠看出。問題是如何根據該序列生成下一個有序的序列呢？下一個有序序列在字典序上剛剛好大於前一個序列，應該是1 3 2，可用看出是將第一個序列中的2和3交換位置得到。而1 3 2之後的下一個序列是2 1 3，是將最後一個2放到了1的前面。在2 1 3之後是2 3 1，是在2 1 3的基礎上將最後的3換到了1的前面。一個很直觀的感覺就是從後向前查找，遇到合適的數的時候與前面某一個數字交換。
具體算法描述，以數字集合{1,2,3}為例：
1，第一個序列就是當前集合元素連起來本身。
2，從後向前查找後面的數大於前面的數對（從小到大，稱其為逆序對），找不到說明所有的排列均已經生成（即從123到了321），若找到（例如2 1 3中的 1和3就是一個逆序對）則停下來。
3，以213為例，就是記住3的位置為i，再從後向前查找數，要找到剛剛好大於1（位置為i-1）的數，這裡很顯然還是3。
4，交換第三步找到的數與位置為i-1的數。
5，逆置從位置i開始到集合結尾的所有的數，例如從*****321（位置i為3）到*****123（位置i為1）。
6，重復這一過程，直到找不到逆序對，則生成了所有的序列。
簡單示例代碼
[cpp]
void swap(int *p,int*q)
{
int tmp;
tmp=*p;
*p=*q;
*q=tmp;
}
void mknewseq(int *data,int start, int last)
{
while(start<last)
{
swap(&data[start],&data[last]);
start++;
last--;
}
}
void showdata(int *data,int num)
{
int i=0;
for(i=0;i<num;i++)
{
printf(" %d ",data[i]);
}
printf("\n");
}
int findall(int *data,int num)
{
int i,j;
int lastdata=num-1;
int tmp;
for(i=lastdata;i>0;i--)
{
if(data[i]>data[i-1]) break;
}
if(0==i) return 0;
tmp=i;
for(j=lastdata;j>=i;j--)
{
if((data[j]>data[i-1])&&(data[j]<data[tmp]))
tmp=j;
}
swap(&data[tmp],&data[i-1]);
mknewseq(data,i,lastdata);
return 1;
}
int main()
{
int data[4]={1,2,3,4};
showdata(data,4);
while(findall(data,4)){
showdata(data,4);
}
return 0;
}
