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.




 
<?php
function get_subset($binary, $arr) {
  // based on true/false values in $binary array, include/exclude
  // values from $arr
  $subset = array();
  foreach (range(0, count($arr)-1) as $i) {
    if ($binary[$i]) {
      $subset[] = $arr[count($arr) - $i - 1];
    } 
  }
  return $subset;
}
 
function print_array($arr) {
  if (count($arr) > 0) {
    echo join(" ", $arr);
  } else {
    echo "(empty)";
  }
  echo '<br>';
}
 
function print_power_sets($arr) {
  echo "POWER SET of [" . join(", ", $arr) . "]<br>";
  foreach (power_set($arr) as $subset) {
    print_array($subset);
  }
}
 
function power_set($arr) {  
  $binary = array();
  foreach (range(1, count($arr)) as $i) {
    $binary[] = false;
  }
  $n = count($arr);
  $powerset = array();
 
  while (count($binary) <= count($arr)) {
    $powerset[] = get_subset($binary, $arr);
    $i = 0;
    while (true) {
      if ($binary[$i]) {
        $binary[$i] = false;
        $i += 1;
      } else {
        $binary[$i] = true;
        break;
      }
    }
    $binary[$i] = true;
  }
 
  return $powerset;
}
 
print_power_sets(array());
print_power_sets(array('singleton'));
print_power_sets(array('dog', 'c', 'b', 'a'));
?>
 