Power Set

powerset.rb

def power_set(set)
  
  # Base Case: The power set of the empty set is a set with only the empty set [ [] ]
  return [set] if set.empty?
  
  # General Case: PS(set): PS(set - element) UNION [ element UNION for each subset in PS(set-element) ]
  ps = power_set(set[1..-1])
  ps | ps.map { |subset| [set[0]] | subset }
end

power_set([1,2,3,4,5,6])
# [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3], [4], [1, 4], [2, 4], [1, 2, 4], [3, 4], [1, 3, 4], [2, 3, 4], [1, 2, 3, 4], [5], [1, 5], [2, 5], [1, 2, 5], [3, 5], [1, 3, 5], [2, 3, 5], [1, 2, 3, 5], [4, 5], [1, 4, 5], [2, 4, 5], [1, 2, 4, 5], [3, 4, 5], [1, 3, 4, 5], [2, 3, 4, 5], [1, 2, 3, 4, 5], [6], [1, 6], [2, 6], [1, 2, 6], [3, 6], [1, 3, 6], [2, 3, 6], [1, 2, 3, 6], [4, 6], [1, 4, 6], [2, 4, 6], [1, 2, 4, 6], [3, 4, 6], [1, 3, 4, 6], [2, 3, 4, 6], [1, 2, 3, 4, 6], [5, 6], [1, 5, 6], [2, 5, 6], [1, 2, 5, 6], [3, 5, 6], [1, 3, 5, 6], [2, 3, 5, 6], [1, 2, 3, 5, 6], [4, 5, 6], [1, 4, 5, 6], [2, 4, 5, 6], [1, 2, 4, 5, 6], [3, 4, 5, 6], [1, 3, 4, 5, 6], [2, 3, 4, 5, 6], [1, 2, 3, 4, 5, 6]]

http://en.wikipedia.org/wiki/Power_set