Monday, November 26, 2007

Powersets in Ruby

Another nifty exercise in Ruby - this one generates all subsets of a given array. Maybe I should have used a set.

# Powerset
# find all subsets of a set

# recursively compute the all subsets of the given set
# based on the idea that for any given subset, either an
# item is in the subset or it isn't
def powerset(set)
  if (set.length == 0)
    return [set]
  end
  result = []
  
  # remove an item from the list
  item = set.shift
  
  # compute the powerset of the smaller list
  sps = powerset(set)
  
  # for each subset, either readd the item or don't
  sps.each do |subset|
    result << subset
    result << (subset + [item])
  end
  return result
end

set = %w{ a b c d }
p = powerset(set)

# sort by length of subset
p.sort! do |a,b|
  a.length - b.length
end

p.each do |subset|
  puts "[#{subset.join(", ")}]"
end