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
// }