Range based for の為の組み合わせ生成イテレータ
以下の例は昔のバージョンです。最新版は github に置いてみました。
実験で、全組合せに対して繰り返し処理をしたい時に使う。
先に使用例。 C++11 以降で使える range-based-for 文を使っているので、 gcc なら -std=c++11 (or -std=c++0x) が必要。
#include <iostream> #include <vector> #include "combinations.hpp" // この記事の下に実装があります。 void printVector(std::vector<size_t> const& v) { for(size_t const i : v) std::cout << i << ' '; std::cout << std::endl; } int main() { Combinations const C(5,3); std::cout << "By iterator" << std::endl; for(auto it = C.begin(); it != C.end(); ++it) printVector(*it); std::cout << "By range-based-for" << std::endl; for(auto const& v : C) printVector(v); }
出力
By iterator 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 By range-based-for 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
コード (ヘッダオンリー) combinations.hpp
。
割と適当なので、間違ってたら誰かが直してくれるはず(おながいします)。
C++11 以降で使える iota を使っているので、
C++98 なら適宜修正のこと(つたわれ)。
#ifndef COMBINATIONS_HPP_INCLUDED #define COMBINATIONS_HPP_INCLUDED #include <iterator> #include <vector> #include <algorithm> #include <cassert> // n から k 個とった組み合わせを生成する. // イテレータに値を生成を任せて、本体は値を保持しない. class Combinations { typedef std::vector<size_t> CombinationType; public: Combinations(size_t n, size_t k) : n_(n), k_(k), initial_(Sequence(k)) { }; class iterator : public std::iterator<std::input_iterator_tag, CombinationType> { public: iterator(size_t n, CombinationType const& seq) : n_(n), seq_(seq) { } iterator(const iterator& it) : n_(it.n_), seq_(it.seq_) { } iterator& operator++() { if(seq_[0] == n_ - seq_.size()) seq_.clear(); else next(); return *this; } iterator operator++(int) { iterator tmp(*this); operator++(); return tmp; } bool operator==(iterator const& rhs) const { return seq_ == rhs.seq_; } bool operator!=(iterator const& rhs) const { return seq_ != rhs.seq_; } CombinationType operator*() const { return seq_; } private: iterator() : n_(0) { }; // forbidden size_t const n_; CombinationType seq_; // seq_ は真単調増加列であるとする. void next() { assert(seq_[0] < (n_ - seq_.size())); size_t const k = seq_.size(); // 配列の後ろから i 番目を順にみて行き、 // 繰り上がりが発生しなくなるまで繰り返す for(size_t i = 0; i < k; ++i) { // 注目している位置 size_t const idx = (k - 1) - i; size_t const vv = seq_[idx]; assert(vv < n_); // 最大値に達していなければ、 // 1 増やして、以降を連番で埋めて、終了 if(vv != (n_ - 1) - i) { for(size_t j = 0; idx+j < k; ++j) seq_[idx+j] = (vv+1) + j; break; } } } }; iterator begin() const { return iterator(n_, Sequence(k_)); } iterator end() const { return iterator(n_, CombinationType()); } private: size_t const n_, k_; CombinationType const initial_; static CombinationType Sequence(size_t n) { CombinationType I(n); std::iota(I.begin(), I.end(), 0); return I; } }; #endif // COMBINATIONS_HPP_INCLUDED
TODO:
std::vector<std::string> const words = { "Alpha", "Beta", "Gamma", "Delta", "Epsilon" }; Combinations C(words, 3);
とかできたらいいよね。