ホーム > libalgo

Range-based for 用クラス (範囲と集合のイテレーション)

概要

集合の方は変態的なビット演算でがんばる.

使い方

range(end)
0, 1, … , end-1
range(start, end)
start, start+1, … , end-1
range(start, end, step)
start, start+step, start+step*2, … , end-1
comb(n,r)
n 個の要素から r 個とる部分集合を辞書順に列挙
subset(S)
S の部分集合を辞書順で大きい方から列挙

実装

class range {
private:
    struct Integer {
        int x, s;
        Integer(int x_, int s_) : x(x_), s(s_) {}
        int operator*() const { return x; }
        bool operator!=(const Integer& o) const { return s > 0 ? x < o.x : x > o.x; }
        void operator++() { x += s; }
    };
    Integer i, n;

public:
    range(int stop) : i(0, 1), n(stop, 1) {}
    range(int start, int stop, int step = 1) : i(start, step), n(stop, step) {}
    Integer begin() { return i; }
    Integer end() { return n; }
};

class comb {
private:
    using ll = long long;
    struct Set {
        ll S;
        Set(ll s) : S(s) {}
        ll operator*() const { return S; }
        bool operator!=(const Set& o) const { return S < o.S; }
        void operator++() {
            ll a = S & -S, b = S + a, c = b & -b;
            S = b | (((c / a) >> 1) - 1);
        }
    };
    Set i, n;

public:
    comb(int n, int r) : i((1LL << r) - 1), n(1LL << n) {}
    Set begin() { return i; }
    Set end() { return n; }
};

class subset {
private:
    using ll = long long;
    struct Set {
        ll s, S;
        bool flg;
        Set(ll s) : s(s), S(s), flg(false) {}
        ll operator*() const { return s; }
        bool operator!=(const Set&) const { return !flg; }
        void operator++() { flg |= (s = (s - 1) & S) == S; }
    };
    Set i, n;

public:
    subset(ll s) : i(s), n(s) {}
    Set begin() { return i; }
    Set end() { return n; }
};

// int main() {
//     // 0 1 2 ... 9
//     for (auto x : range(10)) cout << x << ' ';
//     cout << endl;

//     // 5 6 7 8 9
//     for (auto x : range(5, 10)) cout << x << ' ';
//     cout << endl;

//     // 2 5 8
//     for (auto x : range(2, 10, 3)) cout << x << ' ';
//     cout << endl;

//     // 10 6 2 -2 -6
//     for (auto x : range(10, -10, -4)) cout << x << ' ';
//     cout << endl;

//     // 00111 01011 ... 11100
//     for (auto x : comb(5, 3)) cout << bitset<5>(x) << endl;
//     cout << endl;

//     // 11011 11010 ... 00000
//     for (auto x : subset(21)) cout << bitset<5>(x) << endl;  // 10101
// }

参考文献