RubyでArrayの部分集合を作成する。

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"]]

すごくすっきりしました!