/**
* 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 n Total number of items.
* @param r Number of items chosen.
* @return The number of combinations.
*/
def combinations(n: Long, r: Long): Long =
// Use symmetry: C(n, r) == C(n, n - r)
val k: Long = math.min(r, n - r)
var result: Long = 1
/*
* Compute:
*
* n × (n - 1) × ... × (n - k + 1)
* --------------------------------
* 1 × 2 × ... × k
*
* Dividing at each step keeps intermediate values
* smaller than they would be using factorials.
*/
for i <- 0L until k do
result *= (n - i)
result /= (i + 1)
result
@main def lotteryCombinations(): Unit =
val totalNumbers: Long = 33
val chosenNumbers: Long = 7
val totalCombinations: Long =
combinations(totalNumbers, chosenNumbers)
println(
s"C($totalNumbers, $chosenNumbers) = $totalCombinations"
)
/*
run:
C(33, 7) = 4272048
*/
