Help us understand the problem. What is going on with this article?

Rubyでbit全探索

More than 1 year has passed since last update.

bit全探索

サンプルコード

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

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

EDIT

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

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]

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

使い方

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"]
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした