<?php
function combinations(int $n, int $k):array
{
function combine(int $n, int $k, int $start = 0, array &$result = [], array &$all = [])
{
if ($k == 0) {
$all[] = $result;
return;
}
for ($i = $start; $i <= $n - $k; $i++) {
$result[$k] = $i;
combine($n, $k - 1, $i + 1, $result, $all);
}
}
$res = [];
$all = [];
combine($n, $k, 0, $res, $all);
return $all;
}
function may_add_combination_to_set(array $combination, array $sets)
{
foreach ($sets as $combinationInSet) {
if (count(array_intersect($combinationInSet, $combination)) !== 1) {
return false;
}
}
return true;
}
$combinations = combinations(31, 6);
$sets = [];
foreach ($combinations as $combination) {
if (may_add_combination_to_set($combination, $sets)) {
$sets[] = $combination;
}
}
count($sets);
preferences:
40.85 ms | 402 KiB | 5 Q