C++全排列中遞歸交換法實例詳解
對于求解全排列問題有最暴力的遞歸枚舉法，但是我們希望可以優(yōu)化時間，因此出現(xiàn)了遞歸交換法。
例題
洛谷1706
題目描述
輸出自然數(shù)1到n所有不重復的排列，即n的全排列，要求所產(chǎn)生的任一數(shù)字序列中不允許出現(xiàn)重復的數(shù)字。
輸入格式
一個整數(shù)n。
輸出格式
由1～n組成的所有不重復的數(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進行全排列。當我們交換1和3后，序列變?yōu)?、2、1，如果說這里不排序，直接2、1都保持不動，就輸出3、2、1了，可是我們先要的應該是3、1、2，所以要進行排序。
最后，算一下時間復雜度，我們發(fā)現(xiàn)需要從1到n一位一位的看，之后每位還要枚舉x ~ n，所以總時間復雜度為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語言數(shù)據(jù)結(jié)構(gòu)實例講解單鏈表的實現(xiàn)
單鏈表是后面要學的雙鏈表以及循環(huán)鏈表的基礎，要想繼續(xù)深入了解數(shù)據(jù)結(jié)構(gòu)以及C++，我們就要奠定好這塊基石！接下來就和我一起學習吧2022-03-03
自定義函數(shù): 必須直接或間接在main中調(diào)用，否則該自定義函數(shù)不會被執(zhí)行。 返回值類型 函數(shù)名(參數(shù)類型 參數(shù)名,參數(shù)類型 參數(shù)名...)2017-10-10
平衡二叉樹（Balanced Binary Tree）又被稱為AVL樹（有別于AVL算法），由前蘇聯(lián)的數(shù)學家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉樹，根據(jù)科學家的英文名也稱為AVL樹。本文介紹了它的原理和如何用C++代碼來實現(xiàn)2021-06-06
這篇文章主要給大家介紹了關于C語言漢諾塔的相關資料，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2021-02-02
下面小編就為大家?guī)硪黄獪\談C++中虛函數(shù)實現(xiàn)原理揭秘。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2016-06-06
C++名字空間是一種描述邏輯分組的機制,也就是說,如果有一些聲明按照某種準則在邏輯上屬于同一個模塊,就可以將它們放在同一個名字空間,以表明這個事實,這篇文章主要給大家介紹了關于C++語言中命名空間 (namespace)的相關資料,需要的朋友可以參考下2021-08-08
C++數(shù)據(jù)結(jié)構(gòu)之鏈表的創(chuàng)建
這篇文章主要介紹了C++數(shù)據(jù)結(jié)構(gòu)之鏈表的創(chuàng)建的相關資料,希望通過本文幫助到大家，讓大家理解掌握這部分內(nèi)容，需要的朋友可以參考下2017-10-10
這篇文章主要介紹了C語言中計算二叉樹的寬度的兩種方式的相關資料,需要的朋友可以參考下2017-04-04
本文主要介紹了C++?計算時間差的五種方法小結(jié)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04
成員函數(shù)的重載、覆蓋（override）與隱藏很容易混淆，C++程序員必須要搞清楚概念，否則錯誤將防不勝防2013-10-10