# 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;
\$powerset_of_tail = powerset(\$new_stack, \$tail);
foreach (\$powerset_of_tail as \$e) {
array_push(\$new_stack, \$e);
}
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. Troy says:

Is there a way to do this with large values so that it won’t exhaust the memory?

2. Ted Dziuba says:

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. Richard Cameron says:

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. Joey says:

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. Joey says:

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. Thomas David Baker says:

A more efficient powerset, in haskell, is:

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