A   set   is a collection (container) of certain values,
without any particular order, and no repeated values.

It corresponds with a finite set in mathematics.

A set can be implemented as an associative array (partial mapping)
in which the value of each key-value pair is ignored.

Given a set S, the power set (or powerset) of S, written P(S), or 2S, is the set of all subsets of S.



Task

By using a library or built-in set type, or by defining a set type with necessary operations, write a function with a set S as input that yields the power set 2S of S.



For example, the power set of     {1,2,3,4}     is

 {{}, {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}}.
For a set which contains n elements, the corresponding power set has 2n elements, including the edge cases of empty set.


The power set of the empty set is the set which contains itself (20 = 1):


 





P




{\displaystyle {\mathcal {P}}}

(



∅


{\displaystyle \varnothing }

) = { 



∅


{\displaystyle \varnothing }

 }

And the power set of the set which contains only the empty set, has two subsets, the empty set and the set which contains the empty set (21 = 2):


 





P




{\displaystyle {\mathcal {P}}}

({



∅


{\displaystyle \varnothing }

}) = { 



∅


{\displaystyle \varnothing }

, { 



∅


{\displaystyle \varnothing }

 } }


Extra credit:  Demonstrate that your language supports these last two powersets.




# Based on http://johncarrino.net/blog/2006/08/11/powerset-in-ruby/ 
# See the link if you want a shorter version. 
# This was intended to show the reader how the method works. 
class Array
  # Adds a power_set method to every array, i.e.: [1, 2].power_set
  def power_set
 
    # Injects into a blank array of arrays.
    # acc is what we're injecting into
    # you is each element of the array
    inject([[]]) do |acc, you|
      ret = []             # Set up a new array to add into
      acc.each do |i|      # For each array in the injected array,
        ret << i           # Add itself into the new array
        ret << i + [you]   # Merge the array with a new array of the current element
      end
      ret       # Return the array we're looking at to inject more.
    end
 
  end
 
  # A more functional and even clearer variant.
  def func_power_set
    inject([[]]) { |ps,item|    # for each item in the Array
      ps +                      # take the powerset up to now and add
      ps.map { |e| e + [item] } # it again, with the item appended to each element
    }
  end
end
 
#A direct translation of the "power array" version above
require 'set'
class Set
  def powerset 
    inject(Set[Set[]]) do |ps, item| 
      ps.union ps.map {|e| e.union (Set.new [item])}
    end
  end
end
 
p [1,2,3,4].power_set
p %w(one two three).func_power_set
 
p Set[1,2,3].powerset