かみのメモ

コンピュータビジョン・プログラムな話題中心の勉強メモ

C++で順列・組み合わせを列挙する

競プロとかアルゴリズム系のコードを書いてるとたまに順列・組み合わせを列挙したいことがありますよね。 ということで、この記事では自分なりに書いたC++のコードを紹介してみます。

順列(permutation)その1

まずは {n} 個の要素を並べるときの並べ方のパターンを列挙するコードです。 パターンは全部で {{} _ n \mathrm{P} _ n = n!} 通りあります。

これには<algorithm>にあるnext_permutation()prev_permutation()が使えます。

#include <algorithm>
#include <functional>

#include <iostream>

// nPnの順列に対して処理を実行する
void foreach_permutation(int n, std::function<void(int *)> f) {
  int indexes[n];
  for (int i = 0; i < n; i++) indexes[i] = i;
  do {
    f(indexes);
  } while (std::next_permutation(indexes, indexes + n));
}

int main() {
  foreach_permutation(3, [](int *indexes) {
    std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << std::endl;
  });
}

順列に応じて並び替えられたindexes[]ラムダ式の引数に渡されるので、式の中に順列を利用した処理を書いてあげればよいです。 なお、ラムダ式が導入されたのはC++11以降ですのでコンパイルオプションに--std=c++11などを指定しておく必要があります。

実行結果は以下のようになります。

0,1,2
0,2,1
1,0,2
1,2,0
2,0,1
2,1,0

組み合わせ(combination)

次に {n} 個の要素の中から {k} 個の要素を取り出すときの取り出し方のパターンを列挙するコードです。 パターンは全部で {{} _ n \mathrm{C} _ k} 通りあります。

#include <functional>

#include <iostream>

void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
  if (rest == 0) {
    f(indexes);
  } else {
    if (s < 0) return;
    recursive_comb(indexes, s - 1, rest, f);
    indexes[rest - 1] = s;
    recursive_comb(indexes, s - 1, rest - 1, f);
  }
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
  int indexes[k];
  recursive_comb(indexes, n - 1, k, f);
}

int main() {
  foreach_comb(5, 3, [](int *indexes) {
    std::cout << indexes[0] << ',' << indexes[1] << ',' << indexes[2] << std::endl;
  });
}

recursive_comb再帰的に呼び出すことで、前の値から順に"使うor使わない"を決めていくような実装です。 実行結果は以下のようになります。

0,1,2
0,1,3
0,2,3
1,2,3
0,1,4
0,2,4
1,2,4
0,3,4
1,3,4
2,3,4

順列(permutation)その2

最後に {n} 個の要素の中から {k} 個の要素を取り出し、順番を加味した並べ方のパターンを列挙するコードです。 パターンは合計 {{} _ n \mathrm{P} _ k} 通りですね。

これを実装するためには、先ほどのforeach_permutation()foreach_comb()を組み合わせればよいです。

#include <algorithm>
#include <functional>

#include <iostream>

void recursive_comb(int *indexes, int s, int rest, std::function<void(int *)> f) {
  if (rest == 0) {
    f(indexes);
  } else {
    if (s < 0) return;
    recursive_comb(indexes, s - 1, rest, f);
    indexes[rest - 1] = s;
    recursive_comb(indexes, s - 1, rest - 1, f);
  }
}

// nCkの組み合わせに対して処理を実行する
void foreach_comb(int n, int k, std::function<void(int *)> f) {
  int indexes[k];
  recursive_comb(indexes, n - 1, k, f);
}

// nPnの順列に対して処理を実行する
void foreach_permutation(int n, std::function<void(int *)> f) {
  int indexes[n];
  for (int i = 0; i < n; i++) indexes[i] = i;
  do {
    f(indexes);
  } while (std::next_permutation(indexes, indexes + n));
}

// nPkの順列に対して処理を実行する
void foreach_permutation(int n, int k, std::function<void(int *)> f) {
  foreach_comb(n, k, [&](int *c_indexes) {
    foreach_permutation(k, [&](int *p_indexes) {
      int indexes[k];
      for (int i = 0; i < k; i++) {
        indexes[i] = c_indexes[p_indexes[i]];
      }
      f(indexes);
    });
  });
}

int main() {
  foreach_permutation(
      4, 2, [](int *indexes) { std::cout << indexes[0] << ',' << indexes[1] << std::endl; });
}

実行結果は以下のようになります。

0,1
1,0
0,2
2,0
1,2
2,1
0,3
3,0
1,3
3,1
2,3
3,2

以上、順列・組み合わせを列挙するC++コードを紹介しました。

スポンサーリンク