這篇文章主要介紹了C++全排列中遞歸交換法的示例分析，具有一定借鑒價(jià)值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

創(chuàng)新互聯(lián)建站是一家專業(yè)提供五常企業(yè)網(wǎng)站建設(shè),專注與成都做網(wǎng)站、成都網(wǎng)站制作、H5建站、小程序制作等業(yè)務(wù)。10年已為五常眾多企業(yè)、政府機(jī)構(gòu)等服務(wù)。創(chuàng)新互聯(lián)專業(yè)網(wǎng)站制作公司優(yōu)惠進(jìn)行中。

對(duì)于求解全排列問題有最暴力的遞歸枚舉法，但是我們希望可以優(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

全排列問題——遞歸交換法

其實(shí)跟暴力枚舉思路差不多，每次遞歸枚舉第x個(gè)數(shù)字是幾，之后a[x]可以選擇不動(dòng)，也可以選擇與后面任意一個(gè)數(shù)交換位置，就是從后面選一個(gè)數(shù)放到x的位置上。

簡而言之，就是每到一位就從后面選一個(gè)尚未被使用過的數(shù)字與該位數(shù)字交換，這里有些難理解，您可以自己按照程序推一下樣例。

這樣我們就可以打印所有的全排列了，但這樣不是按順序打印，所以這里需要每次對(duì)a[x] ~ a[n]進(jìn)行排序。

舉個(gè)例子，如對(duì)1、2、3進(jìn)行全排列。當(dāng)我們交換1和3后，序列變?yōu)?、2、1，如果說這里不排序，直接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;
}

感謝你能夠認(rèn)真閱讀完這篇文章，希望小編分享的“C++全排列中遞歸交換法的示例分析”這篇文章對(duì)大家有幫助，同時(shí)也希望大家多多支持創(chuàng)新互聯(lián)，關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，更多相關(guān)知識(shí)等著你來學(xué)習(xí)!

網(wǎng)站欄目：C++全排列中遞歸交換法的示例分析
本文鏈接：http://aaarwkj.com/article22/godsjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、電子商務(wù)、品牌網(wǎng)站建設(shè)、用戶體驗(yàn)、網(wǎng)站建設(shè)、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)