ﾕﾕﾕﾕﾕ

webエンジニアです

深さ優先探索と std::next_permutation でそれぞれ n! 通りの順列を生成する

C++ TIL

　長さ n の順列 [1, 2, ..., n] を並べ替えて n! 個の順列を作りたい。 2<=n<=8 程度として、二通りのやり方を試してみた。

深さ優先探索

　与えられた順列を末尾の要素から再帰的に swap して前通りの組み合わせを試す。ループごとに添字が 1 ずつ増えていくので、計算量は O(n!) と思う。例えば n=10 のときすでに n!=3628800 であるから、パフォーマンスとしてはおよそ最悪である。巡回セールスマン問題¹を全探索で解くとこの計算量になるというから、そのイメージを持つのもいいだろう。

#include<iostream>
using namespace std;

void print(int *a, int len) {
  for (int i = 0; i < len; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}

void dfs(int *a, int j, int len) {
  if (j == len - 1) {
    print(a, len);
    return;
  }

  for (int i = j; i < len; i++) {
    swap(a[i], a[j]);
    dfs(a, j + 1, len);
    swap(a[i], a[j]);
  }
}

int main() {
  int a[] = {1, 2, 3, 4};
  dfs(a, 0, 4);
  return 0;
}

　大小を比較するのではなく機械的に swap を実行しているだけであるから、初期値の並びに関わらず同じ振る舞いをする。同じ要素が含まれていても（順列の定義には反するが）構わずに n! 回計算する。

　ただし初期値を辞書順の並びで渡しても、結果は辞書順にはならない。ふたつの swap で再帰呼び出しを挟んでいるので、辞書順の並びを回復する前に次回の呼び出しが実行されてしまうのだ。もっとも、そもそも O(n!) の計算量を持ってしまうのだから、ソート処理を付け加えてもたいした問題ではない。

`std::next_permutation` を使う

　初めて知る API だったが、結局のところ黙ってこれを使うのがよさそうだ。返り値は bool 型で、次に続く要素が辞書順にみて増加していれば true を返す²。つまり関数を条件文としてそのまま与えてよいし、結果が辞書順の並びとなることが保証される。一方で、順列が単調減少の形となった時点でループは終了してしまうため、 n! 個の要素を列挙するためには初期値が辞書順の並びとなっていなければならない。

#include<iostream>
#include<algorithm>
using namespace std;

void print(int *a, int len) {
  for (int i = 0; i < len; i++) {
    cout << a[i] << " ";
  }
  cout << endl;
}

void perm(int *a, int len) {
  do {
    print(a, len);
  } while (next_permutation(a, a+len));  
}

int main() {
  int a[] = {1, 2, 3, 4};
  perm(a, 4);
  return 0;
}