| 1234567891011121314151617181920212223242526 |
- # Binomial coefficient using Pascal's rule
- #
- # Adapted from the Python version here:
- # https://en.wikipedia.org/wiki/Binomial_coefficient
- #
- # TODO: This could really benefit from logical and/or operators
- fn binomial_coefficient(n: Scalar, k: Scalar) -> Scalar =
- if k < 0
- then 0
- else if k > n
- then 0
- else if k > n - k # Take advantage of symmetry
- then binomial_coefficient(n, n - k)
- else if k == 0
- then 1
- else if 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)
|
