[アルゴリズム]
練習のための問題は 競技プログラミングの履歴, 集合を作りたいけど通常のハッシュだと遅いときに使う
集合の整数表現
わかりやすいリンク
- へ、変態っ！！読めないからやめてっ！bit使ったデータ構造・アルゴリズム実装集
- こういうのはほかにもあるよ、的な
詳しい解説
解説
集合の操作
空集合φ
0
i番目の要素のみからなる集合 {i}
1<<i
n個の要素すべてからなる集合 {0,1,...n-1}
(1 << n) - 1
要素iが集合Sに含まれるか？ i∈S
if (S>>i & 1)
集合Sに要素iを加える S∪{i}
S | 1<<i
集合Sから要素iを取り除く S＼{i}
S &~(1<<i)
集合SとTの和集合
S | T
集合SとTの積集合
S & T
ソースコードに落とし込む
- このようなものは当然誰かが先にやっており、以下のようなC言語バインディングのRubyGemが存在する
- tyler/bitset
- 集合は英語でSetなので、当然BitSetが集合の整数表現の直訳と言えるだろう
- 表現を参考にしつつ自作
class BitSet
attr :s,:len
def initialize(len=32)
@len = len
@s = 0
end
def to_s
@s.to_s(2).rjust(@len,'0')
end
def add(i)
@[email protected]|1<<i
end
def rem(i)
@[email protected]&~(1<<i)
end
def include?(i)
@s>>i&1
end
def union(t)
@s|t
end
def inter(t)
@s&t
end
end
bit全探索
while s < (1<<10) p s.to_s(2) s += 1 end