Arrayの部分集合を作成する必要があったので、作ってみました。
class Array
def subset
rec = Proc.new do |univ|
# subset!でポインタが循環しないようにcloneを使う。
(ret = []) << univ.clone
univ.each do |e|
ret += rec.call(univ - [e])
end
ret
end
rec.call(self).uniq
end
def subset!
self.replace(self.subset)
end
end
他には同じサイズの配列を作成して、その要素を使用するかどうかtrueかfalseのフラグを立てていくという手法もあるようです。
irbで実行するとこうなります。
>> a = %w(1 2 3 4)
=> ["1", "2", "3", "4"]
>> a.subset
=> [["1", "2", "3", "4"], ["2", "3", "4"], ["3", "4"], ["4"], [], ["3"], ["2", "4"], ["2"], ["2", "3"], ["1", "3", "4"], ["1", "4"], ["1"], ["1", "3"], ["1", "2", "4"], ["1", "2"], ["1", "2", "3"]]
2009/7/20 追記
twitterですばらしい方法を教えていただきました!
ただしRuby 1.8.7で追加されたcombinationというメソッドを使用しているので1.8.7以降限定です。
cf. Ruby 1.8.7で使えるようになったRuby 1.9のメソッドたち – (rubikitch loves (Emacs Ruby CUI))
class Array
def subset
(0..self.length).inject([]) do |ret, n|
ret.push(*self.combination(n))
end
end
end
irbでの実行結果。
>> a = %w(1 2 3 4)
=> ["1", "2", "3", "4"]
>> a.subset
=> [[], ["1"], ["2"], ["3"], ["4"], ["1", "2"], ["1", "3"], ["1", "4"], ["2", "3"], ["2", "4"], ["3", "4"], ["1", "2", "3"], ["1", "2", "4"], ["1", "3", "4"], ["2", "3", "4"], ["1", "2", "3", "4"]]
すごくすっきりしました!