PHP Arrays: “power set” and all permutations

Found in the online-version of PHP Cookbook from O’Reilly.

“Power set” = combinations of all or some elements

On one of our development servers (php 5.2.0) we had a problem with the original version of this function, it looked like an endless loop till memory limit exceeded. Here is the rewritten version from Srdjan:

[sourcecode language='php']
public function powerSet($array) {
$results = array(array());
foreach ($array as $j => $element) {
$num = count($results);
for($i=0; $i<$num; $i++) {
array_push($results, array_merge(array($element), $results[$i]));
}
}
return $results;
}
[/sourcecode]

All permutations

[sourcecode language='php']
function pc_permute($items, $perms = array( )) {
if (empty($items)) {
print join(‘ ‘, $perms) . “n”;
} else {
for ($i = count($items) – 1; $i >= 0; –$i) {
$newitems = $items;
$newperms = $perms;
list($foo) = array_splice($newitems, $i, 1);
array_unshift($newperms, $foo);
pc_permute($newitems, $newperms);
}
}
}
[/sourcecode]