前言
最近在數(shù)據(jù)結(jié)構(gòu)的作業(yè)題中工秩，出現(xiàn)了這樣一道題目：
7-2 輸出全排列 (20 分)
請(qǐng)編寫程序輸出前n個(gè)正整數(shù)的全排列（n<10）牵素，并通過9個(gè)測試用例（即n從1到9）觀察n逐步增大時(shí)程序的運(yùn)行時(shí)間坊夫。
輸入格式:
輸入給出正整數(shù)n（n<10）。
輸出格式:
輸出1到n的全排列。每種排列占一行孕豹，數(shù)字間無空格框弛。排列的輸出順序?yàn)樽值湫颉?/p>
輸入樣例:
3
輸出樣例:
123
132
213
231
312
321
在網(wǎng)上搜索了一下辛辨，網(wǎng)上的思路要么很復(fù)雜，要么不能得出正確結(jié)果瑟枫，要么沒有使用遞歸斗搞。
經(jīng)過一番思考后，我發(fā)現(xiàn)了一種新方法慷妙。
先給出此種方法的優(yōu)缺點(diǎn)僻焚，以供參考：
- 優(yōu)點(diǎn)：代碼極短，核心代碼的長度僅有13行膝擂，容易閱讀與理解虑啤。
- 缺點(diǎn)：存在費(fèi)時(shí)費(fèi)力的操作，整個(gè)算法的時(shí)間復(fù)雜度較高架馋，執(zhí)行過程麻煩狞山。
思路
如何將問題轉(zhuǎn)化為遞歸
輸出全排列實(shí)際上可以看做一個(gè)遞歸問題。
假設(shè)有一個(gè)由0~n組成的數(shù)組arr绩蜻，其元素為0铣墨， 1， 2办绝， ... 伊约， n。那么這個(gè)數(shù)組本身其實(shí)就是全排列的第一項(xiàng)孕蝉。
如果要得到全排列的第二項(xiàng)屡律，就需要把第n個(gè)元素和第n - 1個(gè)元素進(jìn)行互換，并在互換后輸出降淮。
如果要得到第三項(xiàng)超埋，就要先得到第n - 2、n - 1佳鳖、n項(xiàng)的全排列霍殴。
……以此類推，得到n個(gè)數(shù)的全排列就可以歸結(jié)為得到n - 1個(gè)數(shù)的全排列系吩，最終歸結(jié)為得到2個(gè)數(shù)的全排列来庭。而得到2個(gè)數(shù)的全排列的方法就是：先將兩個(gè)數(shù)輸出，再將兩個(gè)數(shù)交換后輸出穿挨。
這很顯然可以用遞歸來求解月弛，因?yàn)閱栴}規(guī)模是逐漸減小的肴盏，最終總能減小到一個(gè)特定的情況（遞歸邊界），而且后一次的問題規(guī)模嚴(yán)格小于前一次帽衙，這也是遞歸類問題的典型思路菜皂。
如何減小問題規(guī)模
前面提到了，需要讓問題的規(guī)模逐漸減小厉萝。這里我們以輸出4的全排列為例恍飘，來談?wù)勅绾沃鸩綔p小問題規(guī)模，以及如何用代碼來描述這個(gè)過程冀泻。
按字典序輸出4的全排列常侣，應(yīng)該為：
1234
1243
1324
1342
1423
1432
2134
2143
2314
2341
2413
2431
3124
3142
3214
3241
3412
3421
4123
4132
4213
4231
4312
4321
從中我們不難看出如下規(guī)律：
- 1~4輪流出現(xiàn)在排列的首位
- 排列的第二位從小到大，由1~4中除了首位的數(shù)輪流出現(xiàn)
- 排列的第三位和第四位相當(dāng)于對(duì)兩個(gè)數(shù)進(jìn)行交換輸出（遞歸邊界）
所以我們可以用以下方法逐步減小這個(gè)問題的規(guī)模：
- 循環(huán)掃描一個(gè)由1~n組成的數(shù)組（計(jì)數(shù)變量為i）弹渔，每次把第i個(gè)數(shù)放入數(shù)組的最前面胳施，并保證其他元素的位置相對(duì)不變（如：
1234=>3124） - 對(duì)
i + 1~n的部分進(jìn)行遞歸，在遞歸中再次掃描這個(gè)數(shù)組肢专，仍然進(jìn)行上述變換（如3124=>3214） - 當(dāng)
i + 1 == n時(shí)只剩兩個(gè)數(shù)舞肆，達(dá)到遞歸邊界，輸出這個(gè)數(shù)組 - 交換最后兩個(gè)數(shù)的位置博杖，再輸出一次椿胯，再交換回來
- 遞歸結(jié)束，返回上一層遞歸剃根，將變動(dòng)過的數(shù)字放回去（
3214=>3124哩盲，3124=>1234） - 掃描完從1~n的部分后，全排列輸出完成狈醉，問題解決
偽代碼如下：
void Perm(int ground, int sky) {
if (ground + 1 == sky) {
輸出數(shù)組
交換最后兩數(shù)
輸出數(shù)組
交換最后兩數(shù)
} else {
for (int i = ground; i <= sky; i++) {
對(duì)數(shù)組進(jìn)行變換
Perm(ground + 1, sky);
將變換后的數(shù)組還原
} // for
} // if
} // Perm
因?yàn)檫@個(gè)數(shù)組要一直被使用廉油、一直被變換，所以可以定義成全局變量苗傅。
完整代碼
完整代碼如下抒线，如果gcc編譯不通過可以把對(duì)循環(huán)變量的初始化放在for括號(hào)的外面：
#include <stdio.h>
int arr[15] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
void Perm(int, int);
void Swap(int*, int*);
void PrintArr(int);
void GetArr(int, int);
void BackArr(int, int);
int main() {
int n;
scanf("%d", &n);
Perm(1, n);
return 0;
} // main
/**
* 本程序的核心函數(shù)：遞歸函數(shù)Perm()
*
* @param ground 要處理的數(shù)組元素下標(biāo)的下界
* @param sky 要處理的數(shù)組元素下標(biāo)的上界
*/
void Perm(int ground, int sky) {
if (ground + 1 == sky) { // 遞歸邊界，將最后兩數(shù)先輸出渣慕，再交換后輸出嘶炭，得到一組解
PrintArr(sky);
Swap(&arr[ground], &arr[sky]);
PrintArr(sky);
Swap(&arr[ground], &arr[sky]);
} else { // 其他情況，遍歷逊桦、變換數(shù)組眨猎，并繼續(xù)遞歸求解
for (int i = ground; i <= sky; i++) {
GetArr(i, ground);
Perm(ground + 1, sky); // 遞歸
BackArr(ground, i);
}
}
} // Perm
// 利用地址交換兩個(gè)元素的值
void Swap(int* x, int* y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
} // Swap
void PrintArr(int pos) {
for (int i = 1; i <= pos; i++) {
printf("%d", arr[i]);
}
putchar('\n');
} // PrintArr
// 對(duì)數(shù)組進(jìn)行變換：把位置為nowPos的元素放到targetPos上
void GetArr(int nowPos, int targetPos) { // nowPos > targetPos
int elem = arr[nowPos];
for (int i = nowPos; i >= targetPos; i--) {
arr[i] = arr[i - 1];
}
arr[targetPos] = elem;
} // GetArr
// 將變換后的數(shù)組還原：把位置為nowPos的元素放回targetPos
void BackArr(int nowPos, int targetPos) { // targetPos > nowPos
int elem = arr[nowPos];
for (int i = nowPos; i < targetPos; i++) {
arr[i] = arr[i + 1];
}
arr[targetPos] = elem;
} // BackArr
