C++全配置における再帰的交換法の実例について詳しく説明する。

全配置問題を解くためには最も暴力的な再帰的エニュメレーション法があるが、時間を最適化することが望ましいので、再帰的交換法が現れた。
例題
洛谷1706
テーマの説明
出力自然数1からnまでの全ての重複しない配列、すなわちnの全配列は、生成された任意の数字系列に重複した数字の出現を許可しないことを要求する。
入力フォーマット
一つの整数n
出力フォーマット
1〜nからなるすべての重複しない数字系列は、1行に1つのシーケンスです。
各数字は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です。
最後に、時間の複雑さを計算してみます。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("
");
  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;
}

以上は小编が皆さんに整理してくれたすべての知识です。応援してくれてありがとうございます。