C++で順列・組み合わせを列挙する
競プロとかアルゴリズム系のコードを書いてるとたまに順列・組み合わせを列挙したいことがありますよね。 ということで、この記事では自分なりに書いたC++のコードを紹介してみます。
順列(permutation)その1
まずは、 個の要素を並べるときの並べ方のパターンを列挙するコードです。 パターンは全部で 通りあります。
これには<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)
次に、 個の要素の中から 個の要素を取り出すときの取り出し方のパターンを列挙するコードです。 パターンは全部で 通りあります。
#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
最後に、 個の要素の中から 個の要素を取り出し、順番を加味した並べ方のパターンを列挙するコードです。 パターンは合計 通りですね。
これを実装するには、先ほどの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++コードを紹介しました。
スポンサーリンク