トップ 差分 一覧 ソース 検索 ヘルプ RSS ログイン

集合の整数表現

[アルゴリズム]

練習のための問題は 競技プログラミングの履歴, 集合を作りたいけど通常のハッシュだと遅いときに使う

集合の整数表現

  わかりやすいリンク

  詳しい解説

  解説

集合の操作

集合の整数表現
蟻本 3-2 p.143 より

空集合φ

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
お名前: コメント: