[ruby-list:37114] 配列とべき集合

佐藤と申します。

配列からべき集合をつくるメソッドがないかと検索したら、
ruby-talkにはあったのですが日本語のほうには
なかったのでこちらに投稿(？)しておこうと思います。

[ruby-talk:15903] Re: Subsets of a set

を参考に個人的にいじりました。

#! /usr/bin/env ruby

class Array
  def all_subsets(size)
    if size==0 
      return [[]]
    else    
      prev = all_subsets(size-1)
      res = []
      prev.each do |s|
        self.each do |elem|
          if not s.member?(elem)
            res << s + [elem]
          end
        end
      end     
      res.each do |i| # ここのがないと重複した要素ができてしまう
        i.sort! 
      end     
      return res.uniq
    end
  end

  def power
    a = []  
    for i in 0..(self.length)
      a += self.all_subsets(i)
    end
    a
  end
end

a = [1,2,3] 
p a.all_subsets(2) # => [[1, 2], [1, 3], [2, 3]]
p a.power # => [[], [1], [2], [3], [1, 2], [1, 3], [2, 3], [1, 2, 3]]

いちおう正しく動くと思いますが、
もっといいアルゴリズムがあるのではないかと思います。
そういうのがあったら、もしくは既存のメソッドがあれば
教えてください。

あとall_subsetsのようなのはよく使うと思うので
標準のメソッドでもいいのではないかと思います。

p a.power.power

のような使いかたもできますが、出力量が多すぎるので
正しい結果なのかチェックしていないです。

それでは