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] ]