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"]]
すごくすっきりしました!