冪集合

Rubyで配列の冪集合を返すメソッド。

class Array
  def powerset
    power = []
    bits = Array.new(self.length){|i| 2**i }
    (0..2**self.length-1).each do |i|
      s = []
      bits.map{|j| j & i }.each_with_index do |item, index|
        s.push self[index] unless item == 0
      end
      power.push s
    end
    power
  end
end

検索して見つけた別解

class Array
  def powerset
    ps = []
    0.upto(2**length - 1) do |n|
      a = []
      each do |i|
        a.push i if n & 1 == 1
        n >>= 1
      end
      ps.push a
    end
    ps
  end  
end

こっちの方がスマートだ。あと、selfは省略していいのだけど書かないとなんか据わりが悪い感じ。

実行

require 'pp'
pp [1,2,3,4].powerset

結果。

[[],
 [1],
 [2],
 [1, 2],
 [3],
 [1, 3],
 [2, 3],
 [1, 2, 3],
 [4],
 [1, 4],
 [2, 4],
 [1, 2, 4],
 [3, 4],
 [1, 3, 4],
 [2, 3, 4],
 [1, 2, 3, 4]]