All Possible Subsets

{}, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 } and { 1, 2, 3 }

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

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

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. Is there a way to do this with large values so that it won’t exhaust the memory?

2. 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

3. 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.

4. 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. 🙂

5. 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.

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

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