您好,登錄后才能下訂單哦!
這篇文章主要介紹了C++全排列中遞歸交換法的示例分析,具有一定借鑒價值,感興趣的朋友可以參考下,希望大家閱讀完這篇文章之后大有收獲,下面讓小編帶著大家一起了解一下。
對于求解全排列問題有最暴力的遞歸枚舉法,但是我們希望可以優(yōu)化時間,因此出現(xiàn)了遞歸交換法。
例題
洛谷1706
題目描述
輸出自然數(shù)1到n所有不重復(fù)的排列,即n的全排列,要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。
輸入格式
一個整數(shù)n。
輸出格式
由1~n組成的所有不重復(fù)的數(shù)字序列,每行一個序列。
每個數(shù)字保留 5個場寬。
輸入樣例
3
輸出樣例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
全排列問題——遞歸交換法
其實跟暴力枚舉思路差不多,每次遞歸枚舉第x個數(shù)字是幾,之后a[x]可以選擇不動,也可以選擇與后面任意一個數(shù)交換位置,就是從后面選一個數(shù)放到x的位置上。
簡而言之,就是每到一位就從后面選一個尚未被使用過的數(shù)字與該位數(shù)字交換,這里有些難理解,您可以自己按照程序推一下樣例。
這樣我們就可以打印所有的全排列了,但這樣不是按順序打印,所以這里需要每次對a[x] ~ a[n]進行排序。
舉個例子,如對1、2、3進行全排列。當(dāng)我們交換1和3后,序列變?yōu)?、2、1,如果說這里不排序,直接2、1都保持不動,就輸出3、2、1了,可是我們先要的應(yīng)該是3、1、2,所以要進行排序。
最后,算一下時間復(fù)雜度,我們發(fā)現(xiàn)需要從1到n一位一位的看,之后每位還要枚舉x ~ n,所以總時間復(fù)雜度為O(n!)。
代碼
# include <cstdio> # include <cmath> # include <cstring> # include <algorithm> using namespace std; const int N_MAX = 10; int n; int a[N_MAX + 10]; void permutation(int x) { if (x == n) { for (int i = 1; i <= n; i++) printf("%5d", a[i]); printf("\n"); return; } for (int i = x; i <= n; i++) { sort(a + x, a + n + 1); swap(a[x], a[i]); permutation(x + 1); swap(a[x], a[i]); } } int main() { scanf("%d", &n); for (int i = 1; i <= n; i++) a[i] = i; permutation(1); return 0; }
感謝你能夠認真閱讀完這篇文章,希望小編分享的“C++全排列中遞歸交換法的示例分析”這篇文章對大家有幫助,同時也希望大家多多支持億速云,關(guān)注億速云行業(yè)資訊頻道,更多相關(guān)知識等著你來學(xué)習(xí)!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。