Skip to main content

xsf/scipy_special/
comb.rs

1use num_traits::{PrimInt, Unsigned};
2
3/// $k$-combinations of $n$ things, $_nC_k$
4///
5/// This is often expressed as "$n$ choose $k$".
6///
7/// Pure rust implementation of [`scipy.special.comb(n, k, exact=True)`][comb].
8///
9/// [comb]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html
10///
11/// # Types
12/// - `N`: Any unsigned integer
13///
14/// # See also
15/// - [`comb_rep`]: choosing with replacement
16/// - [`perm`](crate::perm): $k$-permutations of $n$, $_nP_k$
17/// - [`binom`](crate::binom): the binomial coefficient as a floating point function
18#[inline]
19pub fn comb<N: PrimInt + Unsigned>(n: N, k: N) -> N {
20    if n < k {
21        N::zero()
22    } else {
23        choose(n + N::one(), k.min(n - k))
24    }
25}
26
27/// `C(m - 1, k)`, as the product of `(m - j) / j` for `j = 1, ..., k`
28///
29/// This only overflows if the result does.
30fn choose<N: PrimInt + Unsigned>(m: N, k: N) -> N {
31    // manual unrolling because fold and range require the `std::iter::Step` nightly trait
32    let (mut val, mut j) = (N::one(), N::one());
33    while j <= k {
34        val = if let Some(p) = val.checked_mul(&(m - j)) {
35            p / j
36        } else {
37            // `val (m - j)` is a multiple of `j`, so `j / g` divides `m - j`, as it is coprime
38            // to `val / g`; both factors are at most the result
39            let g = gcd(val, j);
40            val / g * ((m - j) / (j / g))
41        };
42        j = j + N::one();
43    }
44    val
45}
46
47/// The greatest common divisor, by Euclid's algorithm
48fn gcd<N: PrimInt>(mut a: N, mut b: N) -> N {
49    while b != N::zero() {
50        (a, b) = (b, a % b);
51    }
52    a
53}
54
55/// $k$-combinations of $n$ things with replacement
56///
57/// Because this (also) counts the number of multisets of size $k$ drawn from an $n$-element set, it
58/// is also known as the *multiset coefficient*, and sometimes expressed as "$n$ multichoose $k$".
59///
60/// It is equivalent to [`comb(n + k - 1, k)`](comb).
61///
62/// Pure rust implementation of [`scipy.special.comb(n, k, exact=True, repetition=True)`][comb].
63///
64/// [comb]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html
65///
66/// # Types
67/// - `N`: Any unsigned integer
68///
69/// # See also
70/// - [`comb`]: $k$-combinations of $n$ without replacement
71/// - [`perm`](crate::perm): $k$-permutations of $n$, $_nP_k$
72/// - [`binom`](crate::binom): the binomial coefficient as a floating point function
73#[inline]
74#[doc(alias = "multiset")]
75#[doc(alias = "multichoose")]
76pub fn comb_rep<N: PrimInt + Unsigned>(n: N, k: N) -> N {
77    if n == N::zero() {
78        if k == n { N::one() } else { N::zero() }
79    } else {
80        choose(n + k, k.min(n - N::one()))
81    }
82}