haar_lib/math/combinatorics/
mod.rs

1//! 組み合わせ論
2
3pub mod bell_number;
4pub mod bell_number_table;
5pub mod bernoulli_number;
6pub mod montmort;
7pub mod partition_number;
8pub mod stirling_first;
9pub mod stirling_first_fixed_k;
10pub mod stirling_first_small_p;
11pub mod stirling_first_table;
12pub mod stirling_second;
13pub mod stirling_second_fixed_k;
14pub mod stirling_second_small_p;
15pub mod stirling_second_table;
16
17pub mod binomial_coefficient;
18
19#[cfg(test)]
20mod tests {
21
22    use crate::math::combinatorics::stirling_first::stirling_first;
23    use crate::math::combinatorics::stirling_first_fixed_k::stirling_first_fixed_k;
24    use crate::math::combinatorics::stirling_first_table::stirling_first_table;
25    use crate::math::combinatorics::stirling_second::stirling_second;
26    use crate::math::combinatorics::stirling_second_fixed_k::stirling_second_fixed_k;
27    use crate::math::combinatorics::stirling_second_table::stirling_second_table;
28    use crate::math::prime_mod::Prime;
29    use crate::num::const_modint::ConstModIntBuilder;
30
31    type P = Prime<998244353>;
32
33    #[test]
34    fn test_stirling_first() {
35        let n = 100;
36
37        let table = stirling_first_table(n, ConstModIntBuilder::<P>::new());
38
39        for (i, ans) in table.iter().enumerate() {
40            let row = stirling_first(i);
41
42            assert_eq!(ans[0..=i], row);
43        }
44
45        for k in 0..=n {
46            let col = stirling_first_fixed_k(n, k);
47            let ans = table.iter().map(|a| a[k]).collect::<Vec<_>>();
48
49            assert_eq!(ans, col);
50        }
51    }
52
53    #[test]
54    fn test_stirling_second() {
55        let n = 100;
56
57        let table = stirling_second_table(n, ConstModIntBuilder::<P>::new());
58
59        for (i, ans) in table.iter().enumerate() {
60            let row = stirling_second(i);
61
62            assert_eq!(ans[0..=i], row);
63        }
64
65        for k in 0..=n {
66            let col = stirling_second_fixed_k(n, k);
67            let ans = table.iter().map(|a| a[k]).collect::<Vec<_>>();
68
69            assert_eq!(ans, col);
70        }
71    }
72}
haar_lib/math/combinatorics/mod.rs

haar_lib/math/combinatorics/
mod.rs
