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}