原博地址：https://www.cnblogs.com/zyoung/p/6764371.html

描述

問題是有一組數(shù)R，需要輸出它的全排列。R的遞歸可定義如下：
當(dāng)個數(shù)n為1時，Perm? = ?，其中r是集合R中唯一的元素
當(dāng)個數(shù)n大于1時，Perm?由(r1)Perm(R1),(r2)Perm(R2),(r3)Perm(R3),…,(rn)Perm(Rn)構(gòu)成
其中Ri = R - {ri} 即該集合中減去對應(yīng)元素

思路

其實說直白點，就是遞歸地把這組數(shù)規(guī)模一個一個地縮小，如1,2,3,4. 先把1固定，遞歸地求2,3,4的全排列，又把2固定，遞歸地求3,4的全排列……直到只剩一個數(shù)，輸出這個排列。
當(dāng)獲取遞歸數(shù)組時，從該組數(shù)的第一個，依次和每一位交換（包括本身），得以產(chǎn)生一個新遞歸數(shù)組（如1,2,3,4，先是1和1交換，產(chǎn)生新的2,3,4）
當(dāng)1和1交換產(chǎn)生的所有遞歸完成之后，實際上已經(jīng)完成了1234，1243，1324，1342，1432，1423的輸出，因為1和自己交換之后，產(chǎn)生了2,3,4
在這個過程中，當(dāng)１,２,３固定時，只有４剩余，所以輸出１,２,３,４.然后固定１,２，交換３,４的位置。輸出１,２,４,３.此時１,２固定的已經(jīng)全部輸出，于是返回到只有１固定，那么此時２需要與３交換位置，再進行1,3固定的遞歸
其實說這么多，還不如一張圖來得實在：

代碼 C++

#include<iostream> using namespace std;void swap(int r[], int i, int j) {int t;t = r[i];r[i] = r[j];r[j] = t; }void perm(int r[], int i, int n) {if (i == n)// 只有一個數(shù)值{for (int j = 0; j <= n; j++){cout << r[j];// 輸出結(jié)果}cout << endl;}else{for (int j = i; j <= n; j++){swap(r, i, j); // 交換r[i]與r[j] perm(r, i + 1, n); // 計算i+1~ n 全排列swap(r, i, j); // 交換r[i]與r[j]}} }int main() {int r[] = { 1,2,3,4 };int i = 0;int n = sizeof(r) / sizeof(r[0]) - 1;perm(r, i, n);system("pause"); }

輸出

1234
1243
1324
1342
1432
1423
2134
2143
2314
2341
2431
2413
3214
3241
3124
3142
3412
3421
4231
4213
4321
4312
4132
4123

總結(jié)

以上是生活随笔為你收集整理的算法设计与分析（第三周）递归实现全排列问题的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。