Ruby selectの条件文らしきところが分からない

Question

###前提・実現したいこと
最大クリーク問題に関するコードで分からない部分があります。

###該当のソースコード

(1...2**n).each do |i|
  grp = n.times.select do |j|
    i >> j & 1 > 0
  end
  if (grp.combination(2).to_a - rels).empty?
    ans = [ans, grp.size].max
  end
end

###試したこと
このコードは全通りのリストを作って、条件に合うものをしらみつぶしに調べるものです。relsは条件のリスト。

grp = n.times.select do |j|
    i >> j & 1 > 0   #ここ
  end

この部分でおそらくパターンを生成しているのですが、このコードの解釈の仕方が分かりません。これはbit演算だと思うのですが、どうしてこのようなコードで全パターン生成できるのでしょうか？

Answer 1

• i >> jはiをj個右シフトします。
• x & 1はxの1の論理積ですが、1は0b1(1bit目のみ1）なので、xの1bit目が1なら1、0なら0になります。つまり、i >> j & 1は「iをj個右シフトしたものの1bit目が1なら1、0なら0」となりますが、j個右シフトしたあとの1bit目は、もともとの数値のj+1bit目になりますので、これは「iのj+1bit目が1なら1、0なら0」という
• x > 0は0より大きいかどうかです。i >> j & 1 >0は「iのj+1bit目が1なら1、0なら0、となる数値が0より大きいかどうか」となり、「iのj+1bit目が1なら真、0なら偽」となります。

つまり、i >> j & 1 >0は数値iのj番目のbit(0番目から始まることに注意)が立っているかどうかです。bitが立っている場合のみselectで選択しているので、

grp = n.times.select do |j|
  i >> j & 1 > 0
end

での、grpは数値iで立っているbitの番号の配列になります。簡単に言うとgrp.map{|x|2**x}.sum == iが成り立つとも言えます。(Array#sumは2.4から追加されたメソッドなので、2.3以下はinject(:+)と書いてください)

なお、iは1...2**nを列挙している物でした。2のn乗以下が保証されているため、n番目以上のbitが立つことはありません。なのでn.timesでは0からn-1まで(nは含まない)の列挙ですが、全てのbitを網羅することができます。

1...2**nは、「0からn-1までの数値の一つ以上取り出したときの組合せ」について、それぞれを○番目のbitとしたときに、全ての数値を網羅していることになります。ですから、全体として、「0からn-1までの数値の一つ以上取り出したときの組合せ」全てを網羅していると言うことになります。n個の頂点があるグラフにおける、頂点の組合せ全てと言えます。

あとは、grp.combination(2).to_aで、その組合せで存在する可能性がある全ての辺の集合をつくって、それが、全て存在するかを確認しているかどうかという風になっています。

アルゴリズム的には最大クリーク問題がNP困難なので全てを回す以外ないと思いますが、大きい方から求めた方が期待される平均時間は短くなるような気がします(最悪時間の計算量は変わりませんが)。

require 'set'
def check(n, rels)
  rels = rels.to_set
  list = n.times.to_a
  (2..n).reverse_each do |i|
    list.combination(i) do |grp|
      return i if grp.combination(2).to_set.subset?(rels)
    end
  end
  return
end

大きい方から求めて、あっていれば早期returnとしています。二重のdoブロックをbrekaで抜けるのが面倒ですので、メソッドにしたほうが楽です。Setを使うと速くなるかどうかは微妙な所です(ハッシュ値生成の方が高コストになる可能性もあるので)。

Answer 2

i >> j & 1 > 0 の式を忠実にたどれば、

演算子の優先順位は、

(右ビットシフト)

&(ビットでの論理積)

(比較演算子)

の順番ですから、

((i>>j) & 1) > 0

の順で計算されます。
したがって、
i >> j で0からn-1まで繰り返し右シフトがおきます。
それぞれの回の右端ビットが判定対象です。

& 1 で、右端ビット以外は0で埋められ、右端ビットが1ならば1を、
0ならば0を返します。つまり、２進数表現でのある桁が1かどうかを
判定します。

> 0で、その右端ビットまでせり出された桁が1ならばtrueを、
0ならばfalseを返し、その繰り返しでgrpの配列がたまっていきます。
例えば、十進数の13、二進数の1101 ならば、{true,false,true,true}の配列が
作られます。
あとは、配列grpからconbinationメソッドで全パターンの組合せを生成し、
先に与えられている配列relsの要素にマッチしたものがあるかどうかで、
マッチする最大個数を残しています。

これが、2のn乗回繰り返され、最後に残ったmaxが、1から2のn乗までの整数の
内でパターンにあう最大個数になります。

Answer 3

私はこのコードが全く分かりませんが

grp = n.times.select do |j|
    i >> j & 1 > 0   #ここ
end

この部分は
0からn-1までの連番配列のうち
jだけ右へシフトした結果が奇数に
なっているものを取り出している
みたいな処理だと私は予想します。

シフト演算子
5-4.ビット演算子

このようにして作った配列から
2個を選んだ時の全組み合わせの配列
を作り、それがrelsと同じ配列だった場合に
ansにansとgrp.sizeを比較して大きい方を
採用しているという感じではないでしょうか。

combination (Array)

付け焼刃で答えているので
間違えている可能性が非常に高いです。