C++全排列中遞歸交換法實(shí)例詳解
對(duì)于求解全排列問(wèn)題有最暴力的遞歸枚舉法，但是我們希望可以?xún)?yōu)化時(shí)間，因此出現(xiàn)了遞歸交換法。
例題
洛谷1706
題目描述
輸出自然數(shù)1到n所有不重復(fù)的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復(fù)的數(shù)字。
輸入格式
一個(gè)整數(shù)n。
輸出格式
由1～n組成的所有不重復(fù)的數(shù)字序列，每行一個(gè)序列。
每個(gè)數(shù)字保留 5個(gè)場(chǎng)寬。
輸入樣例
3
輸出樣例
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
全排列問(wèn)題——遞歸交換法
其實(shí)跟暴力枚舉思路差不多，每次遞歸枚舉第x個(gè)數(shù)字是幾，之后a[x]可以選擇不動(dòng)，也可以選擇與后面任意一個(gè)數(shù)交換位置，就是從后面選一個(gè)數(shù)放到x的位置上。
簡(jiǎn)而言之，就是每到一位就從后面選一個(gè)尚未被使用過(guò)的數(shù)字與該位數(shù)字交換，這里有些難理解，您可以自己按照程序推一下樣例。
這樣我們就可以打印所有的全排列了，但這樣不是按順序打印，所以這里需要每次對(duì)a[x] ~ a[n]進(jìn)行排序。
舉個(gè)例子，如對(duì)1、2、3進(jìn)行全排列。當(dāng)我們交換1和3后，序列變?yōu)?、2、1，如果說(shuō)這里不排序，直接2、1都保持不動(dòng)，就輸出3、2、1了，可是我們先要的應(yīng)該是3、1、2，所以要進(jìn)行排序。
最后，算一下時(shí)間復(fù)雜度，我們發(fā)現(xiàn)需要從1到n一位一位的看，之后每位還要枚舉x ~ n，所以總時(shí)間復(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;
}
以上就是小編給大家整理的全部相關(guān)知識(shí)點(diǎn)，感謝大家對(duì)腳本之家的支持。
相關(guān)文章
《C++ Primer》隱式類(lèi)類(lèi)型轉(zhuǎn)換學(xué)習(xí)整理
在本篇文章里小編給大家整理的是關(guān)于《C++ Primer》隱式類(lèi)類(lèi)型轉(zhuǎn)換學(xué)習(xí)筆記內(nèi)容，需要的朋友們參考下。2020-02-02
這篇文章主要介紹了C++私有繼承，在私有繼承當(dāng)中，基類(lèi)的公有成員和保護(hù)成員都會(huì)成為派生類(lèi)的私有成員。這意味著基類(lèi)的方法都會(huì)被private關(guān)鍵字描述，我們可以在派生類(lèi)中使用它，但類(lèi)對(duì)象無(wú)法直接調(diào)用，下面來(lái)看看詳細(xì)內(nèi)容吧2022-08-08
C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序
這篇文章主要給大家介紹了關(guān)于C++/GoLang如何實(shí)現(xiàn)自底向上的歸并排序的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
C++語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 串的基本操作實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu) 串的基本操作實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-04-04
C++中四種對(duì)象生存期和作用域以及static的用法總結(jié)分析
以下是對(duì)C++中四種對(duì)象生存期和作用域以及static的用法進(jìn)行了詳細(xì)的介紹，需要的朋友可以過(guò)來(lái)參考下2013-09-09
一盤(pán)王者的時(shí)間用C語(yǔ)言實(shí)現(xiàn)三子棋
相信我們都玩過(guò)三子棋，規(guī)則很簡(jiǎn)單，但想用c語(yǔ)言做出這個(gè)游戲，事實(shí)上也是比較簡(jiǎn)單的，下面通過(guò)c語(yǔ)言進(jìn)行對(duì)五子棋的分析2022-02-02
C語(yǔ)言編程之三個(gè)方法實(shí)現(xiàn)strlen函數(shù)
本篇文章是C語(yǔ)言編程篇，主要為大家介紹C語(yǔ)言編程中實(shí)現(xiàn)strlen函數(shù)的三個(gè)方法講解，有需要的朋友可以借鑒參考下，希望可以有所幫助2021-09-09
C語(yǔ)言實(shí)現(xiàn)JSON解析器的方法步驟
JSON是一種非常流行的數(shù)據(jù)格式,本文主要介紹了C語(yǔ)言實(shí)現(xiàn)JSON解析器的方法步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2024-08-08
C語(yǔ)言將音視頻時(shí)鐘同步封裝成通用模塊的方法
視頻的時(shí)鐘基于視頻幀的時(shí)間戳，由于視頻是通過(guò)一定的幀率渲染的，采用直接讀取當(dāng)前時(shí)間戳的方式獲取時(shí)鐘會(huì)造成一定的誤差，精度不足，這篇文章主要介紹了c語(yǔ)言將音視頻時(shí)鐘同步封裝成通用模塊,需要的朋友可以參考下2022-09-09
這篇文章主要介紹了Clion配置C語(yǔ)言環(huán)境的步驟詳解,本文分步驟通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-02-02