| 1234567891011121314151617181920 |
- # Binomial coefficient using Pascal's rule
- #
- # Adapted from the Python version here:
- # https://en.wikipedia.org/wiki/Binomial_coefficient
- fn binomial_coefficient(n: Scalar, k: Scalar) -> Scalar =
- if k < 0 || k > n
- then 0
- else if k > n - k # Take advantage of symmetry
- then binomial_coefficient(n, n - k)
- else if k == 0 || n <= 1
- then 1
- else binomial_coefficient(n - 1, k) + binomial_coefficient(n - 1, k - 1)
- assert_eq(binomial_coefficient(10, 0), 1)
- assert_eq(binomial_coefficient(10, 1), 10)
- assert_eq(binomial_coefficient(10, 2), 45)
- assert_eq(binomial_coefficient(10, 6), 210)
- assert_eq(binomial_coefficient(10, 9), 10)
- assert_eq(binomial_coefficient(10, 10), 1)
|
