Skip to main content

xsf/scipy_special/
stirling.rs

1use num_traits::{PrimInt, Unsigned};
2
3pub trait Stirling2Output: crate::sealed::Sealed {
4    fn stirling2(n: u32, k: u32) -> Self;
5}
6
7macro_rules! impl_stirling2_exact {
8    ($($T:ty),*) => {$(
9        impl Stirling2Output for $T {
10            #[inline]
11            fn stirling2(n: u32, k: u32) -> Self {
12                stirling2_exact(n, k)
13            }
14        }
15    )*};
16}
17
18impl_stirling2_exact!(u8, u16, u32, u64, u128, usize);
19
20impl Stirling2Output for f64 {
21    #[inline]
22    fn stirling2(n: u32, k: u32) -> Self {
23        crate::xsf::stirling2_float(n.into(), k.into())
24    }
25}
26
27/// Stirling number of the second kind $S(n,k)$
28///
29/// Stirling numbers of the second kind count the number of ways to partition a set with $n$
30/// elements into $k$ non-empty subsets.
31///
32/// For an unsigned integer return type `T`, this is a pure rust translation of
33/// [`scipy.special.stirling2(n, k, exact=True)`][stirling2].
34///
35/// For `T = f64`, this corresponds to [`scipy.special.stirling2(n, k, exact=False)`][stirling2],
36/// which uses dynamic programming for $n \le 219$ ($n \le 50$ in SciPy), and else the asymptotic
37/// approximation of Temme \[1\] (relative error $\sim 10^{-6}$, worse for $k$ close to $n$).
38///
39/// [stirling2]: https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.stirling2.html
40///
41/// \[1\] N. M. Temme, "Asymptotic estimates of Stirling numbers", Studies in Applied Mathematics,
42///     89(3):233-243, 1993.
43///
44/// # Examples
45///
46/// ```
47/// use xsf::stirling2;
48///
49/// assert_eq!(stirling2::<u64>(10, 3), 9_330);
50/// assert_eq!(stirling2::<u64>(10, 0), 0);
51/// assert_eq!(stirling2::<u64>(9, 3), 3_025);
52///
53/// // won't fit in u64
54/// assert_eq!(stirling2::<u128>(42, 4), 805_932_309_912_663_709_372_025);
55///
56/// // won't fit in u128
57/// assert_eq!(stirling2::<f64>(50, 10), 2.615_471_651_586_288e43);
58/// ```
59///
60/// # Types
61/// - `T` (required): unsigned integer or `f64` return type
62///
63/// # See also
64/// - [`comb`](crate::comb): $k$-combinations of $n$ things, $_nC_k$
65/// - [`perm`](crate::perm): $k$-permutations of $n$ things, $_nP_k$
66///
67/// # Panics
68/// - For an integer `T`, this function will panic if the result does not fit in type `T`.
69#[must_use]
70#[inline]
71pub fn stirling2<T: Stirling2Output>(n: u32, k: u32) -> T {
72    T::stirling2(n, k)
73}
74
75#[inline]
76fn stirling2_exact<T: PrimInt + Unsigned>(n: u32, k: u32) -> T {
77    if n == k || (n > 0 && k == 1) {
78        return T::one();
79    } else if n < k || k == 0 {
80        return T::zero();
81    } else if k == 2 {
82        // S(n, 2) = 2^(n-1) - 1
83        return 129_u32
84            .checked_sub(n)
85            .and_then(|shift| T::from(u128::MAX >> shift))
86            .unwrap();
87    } else if n == k + 1 {
88        // S(n, n-1) = C(n, 2) = n(n-1)/2
89        return T::from(u128::from(n) * (u128::from(n) - 1) / 2).unwrap();
90    }
91
92    let k = k as usize;
93    let mut n_row = vec![T::one(); k];
94    for i in 2..n as usize {
95        for j in (1..i.min(k)).rev() {
96            n_row[j] = T::from(j + 1).unwrap() * n_row[j] + n_row[j - 1];
97        }
98    }
99    n_row[k - 1]
100}