c++ で「組み合わせ」 #C++

C++ 標準ライブラリの順列で next_permutation があるなら next_combination があっても良いよね！とか思ってたら無かったので、組み合わせ関数を書いてみたのです。

イテレータとかの対応はしようと思ってたけどめんどくさくなった感じで。

#include <iostream>
#include <cstdlib>
#include <functional>
#include <vector>
#include <stack>

  void EnumerateCombination(
      const int *first, const int *const end, const int r,
      std::function<void(const std::vector<int> &)> callback) {
    using T = int;

    std::vector<int> pre;
    pre.resize(r);

    struct Stack {
      int iPre;
      const T *_f;
      int r;
    };
    std::stack<Stack> _stack;

    _stack.push({0, first, r});

    while (_stack.empty() == false) {
      auto curr = _stack.top();
      _stack.pop();

      if (curr.r == 0) {
        callback(pre);
        continue;
      }

      if (curr._f + curr.r == end) {
        pre.resize(curr.iPre);  //ここがちょっとアレ
        pre.insert(pre.end(), curr._f, end);  
        callback(pre);
        continue;
      }

      if (curr._f == end) {
        continue;
      }

      _stack.push({curr.iPre, curr._f + 1, curr.r});
      pre[curr.iPre] = *curr._f;
      _stack.push({curr.iPre + 1, curr._f + 1, curr.r - 1});
    }
  }

int main()
{
  int array[] = {1,2,3,4,5};

  auto callback = [](const std::vector<int> &vec){
    for(auto i : vec) {
      std::cout << i << ",";
    };
    std::cout << std::endl;
  };

  EnumerateCombination(array, array + 5, 3, callback);

  return 0;
}

1,2,3,
1,2,4,
1,2,5,
1,3,4,
1,3,5,
1,4,5,
2,3,4,
2,3,5,
2,4,5,
3,4,5,

説明すると、再帰的に処理してるだけ。再帰関数を使うとスタックオーバーフローするので普通の stack を利用してます。

で、たとえば ABCDE のうちから 3 つを取り出す場合だと、
まず、指定された通りの情報をスタックに積む。

=> ({},{ABCDE},3)

ここで、スタック情報は

第一引数は確定した要素列。
第二引数は組み合わせに使用する要素列。
第三引数は第二引数で指定した要素列から取得する要素数。

として書いてます。

で、次にスタックから一つ取り出して、最初の一要素を除いたもの、最初の一要素を確定させたもの、の２つをスタックに積む。

=> ({},{BCDE},3) + ({A},{BCDE},2)

繰り返し。

=> ({},{BCDE},3) + ({A},{CDE},2) + ({AB},{CDE},1) 
=> ({},{BCDE},3) + ({A},{CDE},2) + ({AB},{DE},1)  + ({ABC},{DE}, 0)

スタックから取り出したら第三引数が 0 なのでコールバック

=> ({},{BCDE},3) + ({A},{CDE},2) + ({AB},{DE},1) 、callback ({ABC})

繰り返し

=> ({},{BCDE},3) + ({A},{CDE},2) + ({AB},{E},1)   + ({ABD},{}, 0)
=> ({},{BCDE},3) + ({A},{CDE},2) + ({AB},{E},1)  、callback({ABD})

スタックから取り出したら第三引数と第二引数の要素数が同じなのでコールバック

=> ({},{BCDE},3) + ({A},{CDE},2)、callback({ABE})

繰り返し

=> ({},{BCDE},3) + ({A},{DE},2)  + ({AC},{DE},1) 
=> ({},{BCDE},3) + ({A},{DE},2)  + ({AC},{E},1)   + ({ACD},{},0) 
=> ({},{BCDE},3) + ({A},{DE},2)  + ({AC},{E},1)  、callback({ACD}) 
=> ({},{BCDE},3) + ({A},{DE},2) 、callback({ACE})
=> ({},{BCDE},3)、callback({ADE})
...

以上。

c++ で 「組み合わせ」

c++ で「組み合わせ」