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+1
bit目になりますので、これは「i
のj+1
bit目が1なら1、0なら0」という
x > 0
は0
より大きいかどうかです。i >> j & 1 >0
は「i
のj+1
bit目が1なら1、0なら0、となる数値が0より大きいかどうか」となり、「i
のj+1
bit目が1なら真、0なら偽」となります。
つまり、i >> j & 1 >0
は数値i
のj
番目のbit(0番目から始まることに注意)が立っているかどうかです。bitが立っている場合のみselectで選択しているので、
Ruby
1grp = n.times.select do |j|
2 i >> j & 1 > 0
3end
での、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困難なので全てを回す以外ないと思いますが、大きい方から求めた方が期待される平均時間は短くなるような気がします(最悪時間の計算量は変わりませんが)。
Ruby
1require 'set'
2def check(n, rels)
3 rels = rels.to_set
4 list = n.times.to_a
5 (2..n).reverse_each do |i|
6 list.combination(i) do |grp|
7 return i if grp.combination(2).to_set.subset?(rels)
8 end
9 end
10 return
11end
大きい方から求めて、あっていれば早期returnとしています。二重のdoブロックをbrekaで抜けるのが面倒ですので、メソッドにしたほうが楽です。Setを使うと速くなるかどうかは微妙な所です(ハッシュ値生成の方が高コストになる可能性もあるので)。
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。