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}