C++でcombination

STLにはnext_permutaionが用意されているが, next_combinationはない. かつてBoostにはboost/alogorithm/combination.hppというものがあったようだが, 標準装備ではなさそうである (ざっとみてみたが, 下記のものがどうもそれらしい).

https://github.com/hyrise/hyrise/blob/master/third_party/boost/algorithm/combination.hpp

ただ何も考えずにただ実現すれば良いのであれば, 再起を使ってわりと簡単に書ける.

#include <iostream>
#include <vector>

template <typename Tlist, typename Tfunc>
void __combination(
    Tlist const& list, typename Tlist::size_type const n, Tfunc const& func,
    Tlist& tmp, typename Tlist::size_type const i, typename Tlist::size_type const j)
{
    if (i == n)
    {
        func(tmp);
        return;
    }

    for (typename Tlist::size_type k = j; k != list.size() + (1 + i- n); ++k)
    {
        tmp[i] = list[k];
        __combination(list, n, func, tmp, i + 1, k + 1);
    }
}

template <typename Tlist, typename Tfunc>
void combination(
    Tlist const& list, typename Tlist::size_type const n, Tfunc const& func)
{
    Tlist tmp(n);
    __combination(list, n, func, tmp, 0, 0);
}

int main()
{
    std::vector<unsigned int>::size_type m = 5, n = 3;
    std::vector<unsigned int> list(m);
    for (unsigned int i = 0; i < m; ++i)
    {
        list[i] = i + 1;
    }

    combination(
        list, n, [](std::vector<unsigned int> const& a) {
            for (auto i(a.begin()); i != a.end(); ++i)
                std::cout << (*i) << "";
            std::cout << std::endl; });
}

コンパイルして実行すると以下のようになるはずである.

$ g++ -std=c++11 combination.cpp
$ ./a.out
123
124
125
134
135
145
234
235
245
345

ラムダ式のところでC++11を必要とするようだが, それ以外のところではC++11じゃなくてもいけるはずだ.

http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n
http://www.programming-magic.com/20090123132035/

ちなみにPythonであれば標準関数が使えるので:

import itertools

m, n = 5, 3
l = [i + 1 for i in range(m)]

for a in itertools.combinations(l, n):
    print("".join(str(i) for i in a))

とかなんとかでいける.

http://docs.python.jp/3/library/itertools.html#itertools.combinations

さらに重複組み合せの場合は上のコードに少し手を加えれば良い.

$ diff combination.cpp repeated_combination.cpp 
16c16
<     for (typename Tlist::size_type k = j; k != list.size() + (1 + i- n); ++k)
---
>     for (typename Tlist::size_type k = j; k < list.size(); ++k)
19c19
<         __combination(list, n, func, tmp, i + 1, k + 1);
---
>         __combination(list, n, func, tmp, i + 1, k);