- Edited
Huh. That function is doing two jobs. Should be two functions.
function selections(int $t, int $n)
{
if($n == 0) {
yield [];
} elseif($t == 0) {
yield array_fill(0, $n, false);
} elseif($t == $n) {
yield array_fill(0, $n, true);
} else {
foreach(selections($t - 1, $n - 1) as $s) {
yield [true, ...$s];
}
foreach(selections($t, $n - 1) as $s) {
yield [false, ...$s];
}
}
}
function subsets(int $needed, array $children)
{
// Ensure the indices are normalised.
$children = array_values($children);
$select = fn($kept) => $children[$kept];
foreach(selections($needed, count($children)) as $selection) {
yield array_map($select, array_keys($selection, true));
}
}
$k = 3;
$n = str_split('abcdefg');
foreach(subsets($k, $n) as $subset)
{
echo join($subset) . ' '; // 7!/(3!4!) = 35 different subsets.
}Bonus for getting them in lexicographical order.
Because the recursive part doesn't deal with the set elements directly, it can take some shortcuts and finish earlier.
Note the anonymous function that has been pulled out of the array_map into $select. It's actually been pulled out of the loop to avoid instantiating a whole new Closure object on every iteration (that would be destroyed at the end of the iteration only for another new practically identical object to be created at the start of the next).
