Will.Whim

A weblog by Will Fitzgerald

Powerset in Ruby

I actually needed to use a powerset function (set of all subsets of a set) today in some Ruby testing code I was writing. So I share it with you:

class Array
  def powerset
    if empty?
      [[]]
    else
      ps = self[1..-1].powerset
      ps.map{|i| self[0,1] + i} + ps
    end
  end
end

For example:

>> [1,2,3].powerset
=> [[1, 2, 3], [1, 2], [1, 3], [1], [2, 3], [2], [3], []]

Advertisements

3 responses to “Powerset in Ruby

  1. Lukas Biewald March 3, 2008 at 6:30 pm

    Funny, I was looking for this same thing the other day and found the uglier but non-recursive: inject([[]]){|c,y|r=[];c.each{|i|r<<i;r<<i+[y]};r}

    at http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/

    – Lukas

  2. Abhay Kumar March 4, 2008 at 1:42 pm

    Hi Will,

    Here’s another ugly and non recursive version that I wrote a few months ago that uses a double inject instead of that instantiation of the internal array:

    inject([[]]){|c,y|c.inject([]){|r,i|r+=[i,i+[y]]}}

    also, Dave’s told me to avoid using the << function. I don’t remember exactly what the reason was so I’ll reconfirm today.

    P.S. Hey Luke :)

  3. Will March 4, 2008 at 2:12 pm

    Abhay,

    That’s beautiful. I might prefer

    inject([[]]){|c,y|c.inject([]){|r,i|r+[i,i+[y]]}}

    for its non-destructive call.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: