declare(strict_types=1);
/**
* Computes the number of combinations C(n, r):
*
* C(n, r) = n! / (r! * (n - r)!)
*
* The calculation is performed incrementally to avoid
* computing large factorials.
*
* @param int $n Total number of items.
* @param int $r Number of items chosen.
* @return int Number of combinations.
*/
function combinations(int $n, int $r): int
{
// Use symmetry: C(n, r) = C(n, n - r)
if ($r > $n - $r) {
$r = $n - $r;
}
$result = 1;
/*
* Compute:
*
* n × (n - 1) × ... × (n - r + 1)
* --------------------------------
* 1 × 2 × ... × r
*
* Dividing at each step keeps intermediate values
* smaller and avoids unnecessary overflow.
*/
for ($i = 0; $i < $r; $i++) {
$result *= ($n - $i);
$result = intdiv($result, $i + 1);
}
return $result;
}
const TOTAL_NUMBERS = 33;
const CHOSEN_NUMBERS = 7;
$totalCombinations = combinations(
TOTAL_NUMBERS,
CHOSEN_NUMBERS
);
echo sprintf(
"C(%d, %d) = %d\n",
TOTAL_NUMBERS,
CHOSEN_NUMBERS,
$totalCombinations
);
/*
run:
C(33, 7) = 4272048
*/
