sfcpl/combinatorics/
combination.rs

1use super::binomial_coefficient::BinomialCoefficient;
2use super::permutation::permutation;
3use crate::factorial::Factoriable;
4
5use crate::modint::ModInt;
6
7use cargo_snippet::snippet;
8
9#[snippet(name = "combination")]
10pub fn combination(n: ModInt, k: usize) -> ModInt {
11    if k > n.get() as usize {
12        panic!("n < k, where n in ModInt, k in usize, so cannot calculate n C k")
13    }
14    permutation(n, k) / k.factorial()
15}
16
17#[test]
18fn comb_test() {
19    use num_integer::binomial;
20    let n = ModInt::new(4, 1000000007);
21    let k = 2;
22    assert_eq!(
23        combination(n, k).get(),
24        binomial(n.get() as usize, k) as i64
25    );
26    assert_eq!(combination(ModInt::new(10, 1000000007), 3).get(), 120);
27
28    // let n = ModInt::new(1, 17);
29    // let k = 3;
30    // assert_eq!(combination(n, k).get(), 0); // panic!
31}
32
33#[snippet(name = "combination")]
34pub fn combination_with_table<T: BinomialCoefficient>(table: &T, n: usize, k: usize) -> ModInt {
35    table.binomial(n, k)
36}
37
38#[test]
39fn comb_tbl_test() {
40    use super::binomial_coefficient::{BCTSmallNK, BCTholdN, BCTDP};
41    use num_integer::binomial;
42
43    let tbl = BCTDP::new(10000, 1000000007);
44    assert_eq!(combination_with_table(&tbl, 10, 3).get(), binomial(10, 3));
45    assert_eq!(
46        combination_with_table(&tbl, 100, 100).get(),
47        binomial(100, 100)
48    );
49    assert_eq!(combination_with_table(&tbl, 2, 0).get(), binomial(2, 0));
50
51    let tbl = BCTholdN::new(100, 1000000007);
52    assert_eq!(combination_with_table(&tbl, 100, 3).get(), binomial(100, 3));
53    assert_eq!(combination_with_table(&tbl, 100, 2).get(), binomial(100, 2));
54    assert_eq!(combination_with_table(&tbl, 100, 0).get(), binomial(100, 0));
55
56    let tbl = BCTSmallNK::new(1000, 1000000007);
57    assert_eq!(combination_with_table(&tbl, 10, 3).get(), binomial(10, 3));
58    assert_eq!(
59        combination_with_table(&tbl, 100, 100).get(),
60        binomial(100, 100)
61    );
62    assert_eq!(combination_with_table(&tbl, 2, 0).get(), binomial(2, 0));
63}
sfcpl/combinatorics/combination.rs

sfcpl/combinatorics/
combination.rs
