C++全排列中遞歸交換法怎么用

今天小編給大家分享一下C++全排列中遞歸交換法怎么用的相關知識點，內容詳細，邏輯清晰，相信大部分人都還太了解這方面的知識，所以分享這篇文章給大家參考一下，希望大家閱讀完這篇文章后有所收獲，下面我們一起來了解一下吧。

題目描述

輸出自然數1到n所有不重復的排列，即n的全排列，要求所產生的任一數字序列中不允許出現重復的數字。

輸入格式

一個整數n。

輸出格式

由1～n組成的所有不重復的數字序列，每行一個序列。

每個數字保留 5個場寬。

輸入樣例

3

輸出樣例

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

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

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

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

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

舉個例子，如對1、2、3進行全排列。當我們交換1和3后，序列變為3、2、1，如果說這里不排序，直接2、1都保持不動，就輸出3、2、1了，可是我們先要的應該是3、1、2，所以要進行排序。

最后，算一下時間復雜度，我們發現需要從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++全排列中遞歸交換法怎么用”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。