冪集合
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]]