All Possible Subsets

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);

About this entry

You’re currently reading “ All Possible Subsets ,” an entry on bluebones.net

Published:
2005.08.22
Category:
Programming