べき集合を作ってみた

書き方を失敗したかもしれない。*1
たしか、べき集合を作る手間はO(2^n)なのでそんなに速度を求めても仕方がないかも

#真偽の組み合わせを作る
def make_bools(n)
  bool=[false,true]
  bools=Array.new(n,bool)
  concatter = proc{|xs,ys| xs.map{|x| ys.map{|y| [x,y]}}.inject{|a,b|a+b}}
  Array.new(n,bool).inject{|re,e| concatter[re,e]}.each{|e| e.flatten!}
end

#べき集合をつくる
def make_power_set1(seed)
  taxonomer=proc{|box,flags| box.zip(flags).map{|e| e[0] if e[1]}}
  result=make_bools(seed.size).map{|flags| taxonomer[seed,flags]}
  result.each{|e| e.delete nil} 
  result
end

def make_power_set2(seed)
  taxonomer=proc do |box,flags| 
    result=[]
    box.zip(flags).each{|e| result << e[0] if e[1]}
    result
  end
  make_bools(seed.size).map{|flags| taxonomer[seed,flags]}
end
p make_bools(3)
p seed=%w{a b c d} 
p ps=make_power_set1(seed)
p ps.size
p ps == make_power_set2(seed)

結果

[[false, false, false], [false, false, true], [false, true, false], [false, true, true], [true, false, false], [true, false, true], [true, true, false], [true, true, true]]
["a", "b", "c", "d"]
[[], ["d"], ["c"], ["c", "d"], ["b"], ["b", "d"], ["b", "c"], ["b", "c", "d"], ["a"], ["a", "d"], ["a", "c"], ["a", "c", "d"], ["a", "b"], ["a", "b", "d"], ["a", "b", "c"], ["a", "b", "c", "d"]]
16
true

*1:proc使いすぎ