べき集合を作ってみた
書き方を失敗したかもしれない。*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使いすぎ