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

6 Replies to “All Possible Subsets”

  1. I’ve also done a power set implementation using Gray Codes – I’d like to do a speed comparison but I can’t get your function to output anything but empty arrays.

    my implementation

  2. These sort of ideas can be expressed extremely tersely in functional programming languages. In Erlang, for example, you can rewrite your 20 lines of PHP as:

    powerset([]) -> [[]]
    powerset([H|T]) -> 
    	S = powerset(T),
        S ++ [[H|X]||X <- S].
    

    Of course what this elegance masks is inefficiency. The function is not tail-recursive and you’ll find it consumes memory like there’s no tomorrow. On the other hand it’s extremely pleasant to write code like this and it behaves ok provided you don’t run it on terribly large sets.

  3. I know this is a bit late, but I’ve been doing a bit of speed/functionality testing with some of the PowerSet functions I’ve found, including this one and Ted Dziuba’s, and the method in O’Reilly’s PHP Cookbook. On a dual P4 2.4GHz machine running PHP 4.3.2 and Linux 2.4.11, I got the following results:

    PHP Cookbook: 0.06 seconds at a maximum of 13 elements
    Ted Dziuba: 0.2 seconds at a maximum of 13 elements
    Bluebones.net: 0.08 seconds at 13 elements, 0.82 seconds at a maximum of 16 elements

    In terms of speed, the PHP Cookbook method slightly outperforms Bluebones.net and outperforms Ted Dziuba. However, in terms of functionality, Bluebones.net is an obvious winner, being able to generate power sets for larger sets than the others. I think Ted Dziuba is the winner in terms of mathematical creativity, though. 🙂

  4. Oh, and by the way – the results for Ted Dziuba’s method were using curly braces instead of square braces, as he mentions in his post. With square brackets it’s quite a bit slower.

  5. A more efficient powerset, in haskell, is:

    powerset       :: [a] -> [[a]]
    powerset []     = [[]]
    powerset (x:xs) = powerset xs ++ map (x:) (powerset xs)
    

Leave a Reply

Your email address will not be published. Required fields are marked *

This site is protected by reCAPTCHA and the Google Privacy Policy and Terms of Service apply.