All possible subsets of a set is called a “powerset”. So, for the set { 1, 2, 3 } the powerset is:
{}, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 } and { 1, 2, 3 }
One way to generate this set of sets is with the following recursive algorithm:
If S isn't empty: pick the first element and call it "head" call the rest of S "tail" for each element e of the powerset of tail: one element of the powerset of S is e another is e plus head
Some code to generate this in PHP (apart from the empty set) is:
function powerset($stack, $set) { if (! $set) { return array(); } $new_stack = $stack; $tail = $set; $head = array_shift($tail); $powerset_of_tail = powerset($new_stack, $tail); foreach ($powerset_of_tail as $e) { array_push($new_stack, $e); array_push($new_stack, array_merge($e, array($head))); } array_push($new_stack, array($head)); return $new_stack; }
We can add in the empty set and wrap the recursive code in a convenience function:
function get_powerset($set) { $powerset = powerset(array(), $set); array_push($powerset, array()); return $powerset; } $set = array(1, 2, 3); $powerset = get_powerset($set);