use_combinatorics/
counting.rs

1use crate::error::CombinatoricsError;
2
3const fn gcd(mut left: u128, mut right: u128) -> u128 {
4    while right != 0 {
5        let remainder = left % right;
6        left = right;
7        right = remainder;
8    }
9
10    left
11}
12
13/// Returns `n!` using checked `u128` arithmetic.
14///
15/// Overflow begins at `n = 35`.
16///
17/// # Errors
18///
19/// Returns [`CombinatoricsError::FactorialOverflow`] when the result no longer
20/// fits in `u128`.
21///
22/// # Examples
23///
24/// ```rust
25/// use use_combinatorics::factorial;
26///
27/// assert_eq!(factorial(5)?, 120);
28/// # Ok::<(), use_combinatorics::CombinatoricsError>(())
29/// ```
30pub const fn factorial(n: u64) -> Result<u128, CombinatoricsError> {
31    let mut result = 1_u128;
32    let mut factor = 2_u64;
33
34    while factor <= n {
35        result = match result.checked_mul(factor as u128) {
36            Some(value) => value,
37            None => return Err(CombinatoricsError::FactorialOverflow(n)),
38        };
39
40        factor += 1;
41    }
42
43    Ok(result)
44}
45
46/// Returns the number of ordered selections of size `k` from `n` items.
47///
48/// # Errors
49///
50/// Returns [`CombinatoricsError::KExceedsN`] when `k > n`.
51///
52/// Returns [`CombinatoricsError::PermutationOverflow`] when the result no
53/// longer fits in `u128`.
54///
55/// # Examples
56///
57/// ```rust
58/// use use_combinatorics::permutations;
59///
60/// assert_eq!(permutations(5, 3)?, 60);
61/// # Ok::<(), use_combinatorics::CombinatoricsError>(())
62/// ```
63pub const fn permutations(n: u64, k: u64) -> Result<u128, CombinatoricsError> {
64    if k > n {
65        return Err(CombinatoricsError::KExceedsN { n, k });
66    }
67
68    if k == 0 {
69        return Ok(1);
70    }
71
72    let mut result = 1_u128;
73    let mut factor = n - k + 1;
74
75    while factor <= n {
76        result = match result.checked_mul(factor as u128) {
77            Some(value) => value,
78            None => return Err(CombinatoricsError::PermutationOverflow { n, k }),
79        };
80
81        factor += 1;
82    }
83
84    Ok(result)
85}
86
87/// Returns the number of unordered selections of size `k` from `n` items.
88///
89/// # Errors
90///
91/// Returns [`CombinatoricsError::KExceedsN`] when `k > n`.
92///
93/// Returns [`CombinatoricsError::CombinationOverflow`] when the result no
94/// longer fits in `u128`.
95///
96/// # Examples
97///
98/// ```rust
99/// use use_combinatorics::combinations;
100///
101/// assert_eq!(combinations(5, 2)?, 10);
102/// # Ok::<(), use_combinatorics::CombinatoricsError>(())
103/// ```
104pub fn combinations(n: u64, k: u64) -> Result<u128, CombinatoricsError> {
105    if k > n {
106        return Err(CombinatoricsError::KExceedsN { n, k });
107    }
108
109    let choose = k.min(n - k);
110    let mut result = 1_u128;
111    let mut step = 1_u64;
112
113    while step <= choose {
114        let mut numerator = u128::from(n - choose + step);
115        let mut denominator = u128::from(step);
116
117        // Cancel common factors before multiplying so more valid inputs fit in
118        // `u128` without changing the exact result.
119        let numerator_gcd = gcd(numerator, denominator);
120        numerator /= numerator_gcd;
121        denominator /= numerator_gcd;
122
123        let result_gcd = gcd(result, denominator);
124        result /= result_gcd;
125        denominator /= result_gcd;
126
127        debug_assert_eq!(denominator, 1);
128
129        result = result
130            .checked_mul(numerator)
131            .ok_or(CombinatoricsError::CombinationOverflow { n, k })?;
132
133        step += 1;
134    }
135
136    Ok(result)
137}
138
139#[cfg(test)]
140mod tests {
141    use super::{combinations, factorial, permutations};
142    use crate::error::CombinatoricsError;
143
144    #[test]
145    fn computes_factorials() {
146        assert_eq!(factorial(0), Ok(1));
147        assert_eq!(factorial(5), Ok(120));
148        assert_eq!(factorial(10), Ok(3_628_800));
149    }
150
151    #[test]
152    fn reports_factorial_overflow() {
153        assert_eq!(
154            factorial(35),
155            Err(CombinatoricsError::FactorialOverflow(35))
156        );
157    }
158
159    #[test]
160    fn computes_permutations() {
161        assert_eq!(permutations(5, 0), Ok(1));
162        assert_eq!(permutations(5, 3), Ok(60));
163        assert_eq!(permutations(10, 2), Ok(90));
164    }
165
166    #[test]
167    fn computes_zero_length_permutations_at_u64_max() {
168        assert_eq!(permutations(u64::MAX, 0), Ok(1));
169    }
170
171    #[test]
172    fn rejects_invalid_permutations() {
173        assert_eq!(
174            permutations(3, 4),
175            Err(CombinatoricsError::KExceedsN { n: 3, k: 4 })
176        );
177    }
178
179    #[test]
180    fn reports_permutation_overflow() {
181        assert_eq!(
182            permutations(40, 30),
183            Err(CombinatoricsError::PermutationOverflow { n: 40, k: 30 })
184        );
185    }
186
187    #[test]
188    fn computes_combinations() {
189        assert_eq!(combinations(5, 2), Ok(10));
190        assert_eq!(combinations(10, 3), Ok(120));
191        assert_eq!(combinations(52, 5), Ok(2_598_960));
192    }
193
194    #[test]
195    fn rejects_invalid_combinations() {
196        assert_eq!(
197            combinations(3, 4),
198            Err(CombinatoricsError::KExceedsN { n: 3, k: 4 })
199        );
200    }
201
202    #[test]
203    fn reports_combination_overflow() {
204        assert_eq!(
205            combinations(150, 75),
206            Err(CombinatoricsError::CombinationOverflow { n: 150, k: 75 })
207        );
208    }
209}
use_combinatorics/counting.rs

use_combinatorics/
counting.rs
