Rubyでbit全探索

bit全探索

サンプルコード

• bit全探索 is 何？
  • bitを利用して数え上げをする手法

（例）３つの要素がある集合から、任意の要素を選び出すすべての場合を列挙する。

EDIT

@scivola さんからコメントがありました。Array自体にbitの順列を列挙できるメソッドが生えているので、それを使ったほうが良さそうです。コメント欄参照。

• 元のサンプルコード(wandbox)
• サンプルコード(wandbox)

bit_search.rb

len = 3

[0, 1].repeated_permutation(len) do |bits|
  p bits
end

出力
[0, 0, 0]
[0, 0, 1]
[0, 1, 0]
[0, 1, 1]
[1, 0, 0]
[1, 0, 1]
[1, 1, 0]
[1, 1, 1]

これで、１が立っていれば要素を選んだ。０であれば選んでないという列挙ができる。

使い方

• 列挙対象の集合とzipして合算するなど

• サンプルコード(wandbox)

bit_search_sample.rb

SET = ["apple", "google", "amazon"]

cnt = 0
len = 3

while cnt < (1 << len)
  bit = cnt.to_s(2).rjust(len,'0').split("").map(&:to_i)

  sample = []
  SET.zip(bit).each do |test|
    item,b = test.first,test.last
    # bitが1だったら処理
    if b==1 
      sample << item
    end
  end

  p sample

  cnt+=1
end

出力
[]
["amazon"]
["google"]
["google", "amazon"]
["apple"]
["apple", "amazon"]
["apple", "google"]
["apple", "google", "amazon"]