エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

組み合わせ(数学の) 〜 combination

C++

ベクタから指定した個数の要素を持つ部分集合のベクタを生成します。

#include <vector>

template<typename T>
struct Combination
{
    typedef std::vector<T>           source_type;
    typedef std::vector<source_type> values_type;

    Combination(const source_type& source, int n)
    {
        std::vector<int> v(n);
        combination(0, source.size(), n, source, 0, v);
    }

     values_type values;

private:
    void combination(int begin, int size, int n, const source_type& source, int index, std::vector<int>& v)
    {
        if(n == 0)
        {
            v[index] = begin;

            source_type subset;
            for(std::vector<int>::iterator i = v.begin(); i != v.end(); ++i)
            {
                subset.push_back(source[*i]);
            }
            values.push_back(subset);
        }
        else
        {
            for(int i = 0; i < size - n + 1; ++i)
            {
                v[index] = begin + i;
                combination(begin + i + 1, size - i - 1, n - 1, source, index + 1, v);
            }
        }
    }
};

#include <iostream>
#include <algorithm>
#include <iterator>

int main(int, char* [])
{
    std::vector<int> source;
    for(int i = 0; i < 5; ++i)
    {
        source.push_back(i);
    }
    Combination<int> combi(source, 3);

    for(std::size_t row = 0; row < combi.values.size(); ++row)
    {
        std::copy(combi.values[row].begin(), combi.values[row].end(), std::ostream_iterator<int>(std::cout, ""));
        std::cout << "\n";
    }

    return 0;
}


実行結果。

$ ./combi
012
013
014
023
024
034
123
124
134
234

Prolog

permutation/3という述語を定義しています。ライブラリにも同名の述語がありますが、そちらはpermutation/2で個数の指定がありません。

permutation(_, 0, []).
permutation(Xs, N, [Y|Ys]) :-
    select(Y, Xs, Zs),
    N1 is N - 1,
    permutation(Zs, N1, Ys).

combination(Xs, N, Ys) :-
    findall(Z, permutation(Xs, N, Z), Zs),
    maplist(sort, Zs, Ws),
    sort(Ws, Ys).


実行結果。

$ swipl -s combi.prolog -g 'combination([0,1,2,3,4], 3, Y), writeln(Y)' -t halt
[ [0,1,2],[0,1,3],[0,1,4],[0,2,3],[0,2,4],[0,3,4],[1,2,3],[1,2,4],[1,3,4],[2,3,4] ]