devela/num/int/wrapper/impl_combinatorics.rs
1// devela::num::int::wrapper::impl_combinatorics
2//
3//! Implements combinatorics-related methods for [`Int`].
4//
5// TOC
6// - signed|unsigned:
7// - factorial
8// - combine
9// - combine_rep
10// - permute
11// - permute_rep
12
13use super::super::shared_docs::*;
14#[cfg(feature = "cast")]
15use crate::Cast;
16#[cfg(_int_i··)]
17use crate::NumError::NonNegativeRequired;
18use crate::{
19 cfor, iif, paste, Int,
20 NumError::{MismatchedSizes, Overflow},
21 NumResult as Result,
22};
23
24/// Implements combinatorics-related methods for [`Int`].
25///
26/// # Args
27/// $t: the input/output type
28/// $cap: the capability feature that enables the given implementation. E.g "_int_i8".
29///
30/// $d: the doclink suffix for the method name
31macro_rules! impl_combinatorics {
32 () => {
33 impl_combinatorics![signed
34 i8 :"_int_i8" |"",
35 i16 :"_int_i16" |"-1",
36 i32 :"_int_i32" |"-2",
37 i64 :"_int_i64" |"-3",
38 i128 :"_int_i128" |"-4",
39 isize :"_int_isize" |"-5"
40 ];
41 impl_combinatorics![unsigned
42 u8 :"_int_u8" |"-6",
43 u16 :"_int_u16" |"-7",
44 u32 :"_int_u32" |"-8",
45 u64 :"_int_u64" |"-9",
46 u128 :"_int_u128" |"-10",
47 usize :"_int_usize" |"-11"
48 ];
49 };
50 (signed $( $t:ty : $cap:literal | $d:literal ),+) => {
51 $( impl_combinatorics![@signed $t:$cap | $d]; )+
52 };
53 (unsigned $( $t:ty : $cap:literal | $d:literal ),+) => {
54 $( impl_combinatorics![@unsigned $t:$cap | $d]; )+
55 };
56 (
57 // implements signed ops
58 @signed $t:ty : $cap:literal | $d:literal) => { paste! {
59 #[doc = crate::doc_availability!(feature = $cap)]
60 ///
61 #[doc = "# Integer combinatorics related methods for `" $t "`\n\n"]
62 #[doc = "- [factorial](#method.factorial" $d ")"]
63 #[doc = "- [subfactorial](#method.subfactorial" $d ")"]
64 #[doc = "- [permute](#method.permute" $d ")"]
65 #[doc = "- [permute_rep](#method.permute_rep" $d ")"]
66 #[doc = "- [combine](#method.combine" $d ")"]
67 #[doc = "- [combine_rep](#method.combine_rep" $d ")"]
68 ///
69 #[cfg(feature = $cap )]
70 impl Int<$t> {
71 /// Returns the factorial.
72 ///
73 /// Permutations of *n* items, ordered, where $n = r$.
74 ///
75 /// # Formula
76 #[doc = FORMULA_FACTORIAL!()]
77 ///
78 /// These are the maximum numbers whose factorials can fit within
79 /// standard signed integer types:
80 ///
81 /// 5 for `i8`, 7 for `i16`, 12 for `i32`, 20 for `i64` and 33 for `i128`.
82 ///
83 /// # Errors
84 /// Returns [`NonNegativeRequired`] if $n<0$,
85 /// and [`Overflow`] if the result can't fit the type.
86 ///
87 /// # Examples
88 /// ```
89 /// # use devela::Int;
90 #[doc = "assert_eq![Ok(Int(120)), Int(5_" $t ").factorial()];"]
91 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").factorial()];"]
92 #[doc = "assert_eq![Ok(Int(1)), Int(0_" $t ").factorial()];"]
93 #[doc = "assert![Int(-3_" $t ").factorial().is_err()];"]
94 #[doc = "assert![Int(" $t "::MAX).factorial().is_err()];"]
95 /// ```
96 pub const fn factorial(self) -> Result<Int<$t>> {
97 let n = self.0;
98 iif![n < 0; return Err(NonNegativeRequired)];
99 let (mut n, mut result): ($t, $t) = (n.abs(), 1);
100 while n > 1 {
101 result = if let Some(res) = result.checked_mul(n) {
102 res
103 } else {
104 return Err(Overflow(None));
105 };
106 n -= 1;
107 }
108 Ok(Int(result))
109 }
110
111 /// Returns the subfactorial, or the number of derangements.
112 ///
113 /// Permutations of *n* items which no element appears in its original position.
114 ///
115 /// # Formulation
116 /// ## Algorithm
117 /// The current implementation uses the recursive definition:
118 #[doc = ALGORITHM_SUBFACTORIAL!()]
119 ///
120 /// ## Closed-Form Formulas
121 /// Other equivalent formulas for \( !n \) include:
122 ///
123 /// 1. **Summation Formula**:
124 #[doc = FORMULA_SUBFACTORIAL_SUMMATION!()]
125 /// 2. **Approximation Formula**:
126 #[doc = FORMULA_SUBFACTORIAL_APPROXIMATION!()]
127 ///
128 /// These are the maximum numbers whose subfactorials can fit within
129 /// standard signed integer types:
130 ///
131 /// 5 for `i8`, 8 for `i16`, 12 for `i32`, 20 for `i64` and 35 for `i128`.
132 ///
133 /// # Errors
134 /// Returns [`NonNegativeRequired`] if $n<0$,
135 /// and [`Overflow`] if the result can't fit the type.
136 ///
137 /// # Panics
138 /// For very large values (e.g. `i32:MAX`) the stack can overflow.
139 ///
140 /// # Examples
141 /// ```
142 /// # use devela::Int;
143 /// # #[cfg(not(miri))] { // too slow for miri
144 #[doc = "assert_eq![Ok(Int(44)), Int(5_" $t ").subfactorial()];"]
145 #[doc = "assert_eq![Ok(Int(9)), Int(4_" $t ").subfactorial()];"]
146 #[doc = "assert_eq![Ok(Int(1)), Int(0_" $t ").subfactorial()];"]
147 #[doc = "assert![Int(-3_" $t ").subfactorial().is_err()];"]
148 #[doc = "assert![Int(127_" $t ").subfactorial().is_err()];"]
149 /// # }
150 /// ```
151 /// # Links
152 /// - The list of subfactorials is available in <https://oeis.org/A000166>.
153 pub const fn subfactorial(self) -> Result<Int<$t>> {
154 let n = self.0;
155 iif![n < 0; return Err(NonNegativeRequired)];
156 match n {
157 0 => Ok(Int(1)),
158 1 => Ok(Int(0)),
159 _ => {
160 let a = match Self::subfactorial(Int(n - 1)) {
161 Ok(a) => a.0, Err(e) => return Err(e),
162 };
163 let b = match Self::subfactorial(Int(n - 2)) {
164 Ok(b) => b.0, Err(e) => return Err(e),
165 };
166 let sum = a + b; // can't overflow
167 if let Some(res) = (n - 1).checked_mul(sum) {
168 Ok(Int(res))
169 } else {
170 return Err(Overflow(None));
171 }
172 }
173 }
174 }
175
176 /// Combinations of `n` items taken `r` at a time, ordered.
177 ///
178 /// # Formula
179 #[doc = FORMULA_COMBINE!()]
180 ///
181 /// # Errors
182 /// Returns [`NonNegativeRequired`] if $n<0 \lor r<0$,
183 /// [`MismatchedSizes`] if $r > n$, and
184 /// [`Overflow`] if the result cant't fit the type.
185 ///
186 /// # Examples
187 /// ```
188 /// # use devela::Int;
189 #[doc = "assert_eq![Ok(Int(1)), Int(3_" $t ").combine(3)];"]
190 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine(2)];"]
191 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine(1)];"]
192 #[doc = "assert![Int(-3_" $t ").combine(3).is_err()];"]
193 #[doc = "assert![Int(3_" $t ").combine(-2).is_err()];"]
194 /// ```
195 pub const fn combine(self, r: $t) -> Result<Int<$t>> {
196 let n = self.0;
197 iif![n < 0 || r < 0; return Err(NonNegativeRequired)];
198 iif![r > n; return Err(MismatchedSizes)];
199 let (mut num, mut den): ($t, $t) = (1, 1);
200 cfor![i in 0..r => {
201 num = if let Some(res) = num.checked_mul(n - i) {
202 res
203 } else {
204 return Err(Overflow(None))
205 };
206 den = if let Some(res) = den.checked_mul(i + 1) {
207 res
208 } else {
209 return Err(Overflow(None))
210 };
211 }];
212 Ok(Int(num / den))
213 }
214
215 /// Combinations of `n` items taken `r` at a time with repetitions, unordered.
216 ///
217 /// Also known as *multichoose*.
218 ///
219 /// # Formula
220 #[doc = FORMULA_COMBINE_REP!()]
221 ///
222 /// # Errors
223 /// Returns [`NonNegativeRequired`] if $n<0 \lor r<0$,
224 /// [`Overflow`] if the result cant't fit the type.
225 ///
226 /// # Examples
227 /// ```
228 /// # use devela::Int;
229 #[doc = "assert_eq![Ok(Int(10)), Int(3_" $t ").combine_rep(3)];"]
230 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").combine_rep(2)];"]
231 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine_rep(1)];"]
232 #[doc = "assert![Int(-3_" $t ").combine_rep(3).is_err()];"]
233 #[doc = "assert![Int(3_" $t ").combine_rep(-2).is_err()];"]
234 /// ```
235 pub const fn combine_rep(self, r: $t) -> Result<Int<$t>> {
236 let n = self.0;
237 iif![n < 0 || r < 0; return Err(NonNegativeRequired)];
238 let (mut num, mut den): ($t, $t) = (1, 1);
239 cfor![i in 0..r => {
240 let Some(factor) = n.checked_add(r - 1 - i) else {
241 return Err(Overflow(None))
242 };
243 num = if let Some(res) = num.checked_mul(factor) {
244 res
245 } else {
246 return Err(Overflow(None))
247 };
248 den = if let Some(res) = den.checked_mul(i + 1) {
249 res
250 } else {
251 return Err(Overflow(None))
252 };
253 }];
254 Ok(Int(num / den))
255 }
256
257 /// Permutations of `n` items taken `r` at a time, ordered.
258 ///
259 /// When $n=r$ or $n=r-1$ the result is the same as calculating the factorial $n!$.
260 ///
261 /// # Formula
262 #[doc = FORMULA_PERMUTE!()]
263 ///
264 /// # Errors
265 /// Returns [`NonNegativeRequired`] if $n<0 \lor r<0$,
266 /// [`MismatchedSizes`] if $|r| > |n|$, and
267 /// [`Overflow`] if the result cant't fit the type.
268 ///
269 /// # Examples
270 /// ```
271 /// # use devela::Int;
272 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").permute(3)];"]
273 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").permute(2)];"]
274 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").permute(1)];"]
275 #[doc = "assert![Int(-3_" $t ").permute(3).is_err()];"]
276 #[doc = "assert![Int(3_" $t ").permute(-2).is_err()];"]
277 /// ```
278 pub const fn permute(self, r: $t) -> Result<Int<$t>> {
279 let n = self.0;
280 iif![n < 0 || r < 0; return Err(NonNegativeRequired)];
281 iif![r > n; return Err(MismatchedSizes)];
282 let mut result: $t = 1;
283 cfor![i in 0..r => {
284 result = if let Some(res) = result.checked_mul(n - i) {
285 res
286 } else {
287 return Err(Overflow(None))
288 }
289 }];
290 Ok(Int(result))
291 }
292
293 /// Permutations of `n` items taken `r` at a time with repetitions, ordered.
294 ///
295 /// # Formula
296 #[doc = FORMULA_PERMUTE_REP!()]
297 ///
298 /// # Errors
299 /// Returns [`NonNegativeRequired`] if $n<0 \lor r<0$,
300 /// and [`Overflow`] if the result cant't fit the type.
301 ///
302 /// # Examples
303 /// ```
304 /// # use devela::{Int, Num};
305 #[doc = "assert_eq![Ok(Int(27)), Int(3_" $t ").permute_rep(3)];"]
306 #[doc = "assert_eq![Ok(Int(9)), Int(3_" $t ").permute_rep(2)];"]
307 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").permute_rep(1)];"]
308 #[doc = "assert![Int(-3_" $t ").permute_rep(3).is_err()];"]
309 #[doc = "assert![Int(3_" $t ").permute_rep(-2).is_err()];"]
310 /// ```
311 #[cfg(feature = "cast")]
312 #[cfg_attr(feature = "nightly_doc", doc(cfg(feature = "cast")))]
313 pub const fn permute_rep(self, r: $t) -> Result<Int<$t>> {
314 let n = self.0;
315 iif![n < 0 || r < 0; return Err(NonNegativeRequired)];
316 let Ok(r_u32) = Cast(r).checked_cast_to_u32() else {
317 return Err(Overflow(None));
318 };
319 if let Some(res) = n.checked_pow(r_u32) {
320 Ok(Int(res))
321 } else {
322 Err(Overflow(None))
323 }
324 }
325 }
326 }};
327 (
328 // implements unsigned ops
329 @unsigned $t:ty : $cap:literal | $d:literal) => { paste! {
330 #[doc = crate::doc_availability!(feature = $cap)]
331 ///
332 #[doc = "# Integer combinatorics related methods for `" $t "`\n\n"]
333 #[doc = "- [factorial](#method.factorial" $d ")"]
334 #[doc = "- [subfactorial](#method.subfactorial" $d ")"]
335 #[doc = "- [combine](#method.combine" $d ")"]
336 #[doc = "- [combine_rep](#method.combine_rep" $d ")"]
337 #[doc = "- [permute](#method.permute" $d ")"]
338 #[doc = "- [permute_rep](#method.permute_rep" $d ")"]
339 ///
340 #[cfg(feature = $cap )]
341 impl Int<$t> {
342 /// Returns the factorial.
343 ///
344 /// Permutations of *n* items, ordered, where $n = r$.
345 ///
346 /// # Formula
347 #[doc = FORMULA_FACTORIAL!()]
348 ///
349 /// These are the maximum numbers whose factorials can fit within
350 /// standard signed integer types:
351 ///
352 /// 5 for `u8`, 8 for `u16`, 12 for `u32`, 20 for `u64` and 34 for `u128`.
353 ///
354 /// # Errors
355 /// Returns [`Overflow`] if the result can't fit the type.
356 ///
357 /// # Examples
358 /// ```
359 /// # use devela::Int;
360 #[doc = "assert_eq![Ok(Int(120)), Int(5_" $t ").factorial()];"]
361 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").factorial()];"]
362 #[doc = "assert_eq![Ok(Int(1)), Int(0_" $t ").factorial()];"]
363 #[doc = "assert![Int(" $t "::MAX).factorial().is_err()];"]
364 /// ```
365 pub const fn factorial(self) -> Result<Int<$t>> {
366 let [mut n, mut result] = [self.0, 1];
367 while n > 1 {
368 result = if let Some(res) = result.checked_mul(n) {
369 res
370 } else {
371 return Err(Overflow(None));
372 };
373 n -= 1;
374 }
375 Ok(Int(result))
376 }
377
378 /// Returns the subfactorial, or the number of derangements.
379 ///
380 /// Permutations of *n* items which no element appears in its original position.
381 ///
382 /// # Formulation
383 /// ## Algorithm
384 /// The current implementation uses the recursive definition:
385 #[doc = ALGORITHM_SUBFACTORIAL!()]
386 ///
387 /// ## Closed-Form Formulas
388 /// Other equivalent formulas for \( !n \) include:
389 ///
390 /// 1. **Summation Formula**:
391 #[doc = FORMULA_SUBFACTORIAL_SUMMATION!()]
392 /// 2. **Approximation Formula**:
393 #[doc = FORMULA_SUBFACTORIAL_APPROXIMATION!()]
394 ///
395 /// These are the maximum numbers whose subfactorials can fit within
396 /// standard signed integer types:
397 ///
398 /// 5 for `u8`, 8 for `u16`, 13 for `u32`, 20 for `u64` and 35 for `u128`.
399 ///
400 /// # Errors
401 /// Returns [`Overflow`] if the result can't fit the type.
402 ///
403 /// # Panics
404 /// For very large values (e.g. `u32:MAX`) the stack can overflow.
405 ///
406 /// # Examples
407 /// ```
408 /// # use devela::Int;
409 /// # #[cfg(not(miri))] { // too slow for miri
410 #[doc = "assert_eq![Ok(Int(44)), Int(5_" $t ").subfactorial()];"]
411 #[doc = "assert_eq![Ok(Int(9)), Int(4_" $t ").subfactorial()];"]
412 #[doc = "assert_eq![Ok(Int(1)), Int(0_" $t ").subfactorial()];"]
413 #[doc = "assert![Int(255_" $t ").subfactorial().is_err()];"]
414 /// # }
415 /// ```
416 /// # Links
417 /// - The list of subfactorials is available in <https://oeis.org/A000166>.
418 pub const fn subfactorial(self) -> Result<Int<$t>> {
419 let n = self.0;
420 match n {
421 0 => Ok(Int(1)),
422 1 => Ok(Int(0)),
423 _ => {
424 let a = match Self::subfactorial(Int(n - 1)) {
425 Ok(a) => a.0, Err(e) => return Err(e),
426 };
427 let b = match Self::subfactorial(Int(n - 2)) {
428 Ok(b) => b.0, Err(e) => return Err(e),
429 };
430 let sum = a + b; // can't overflow
431 if let Some(res) = (n - 1).checked_mul(sum) {
432 Ok(Int(res))
433 } else {
434 return Err(Overflow(None));
435 }
436 }
437 }
438 }
439
440 /// Combinations of `n` items taken `r` at a time, unordered.
441 ///
442 /// # Formula
443 #[doc = FORMULA_COMBINE!()]
444 ///
445 /// # Errors
446 /// Returns [`MismatchedSizes`] if $r > n$ and
447 /// [`Overflow`] if the result cant't fit the type.
448 ///
449 /// # Examples
450 /// ```
451 /// # use devela::Int;
452 #[doc = "assert_eq![Ok(Int(1)), Int(3_" $t ").combine(3)];"]
453 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine(2)];"]
454 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine(1)];"]
455 #[doc = "assert![Int(" $t "::MAX).combine(" $t "::MAX).is_err()];"]
456 /// ```
457 pub const fn combine(self, r: $t) -> Result<Int<$t>> {
458 let n = self.0;
459 iif![r > n; return Err(MismatchedSizes)];
460 let (mut num, mut den): ($t, $t) = (1, 1);
461 cfor![i in 0..r => {
462 num = if let Some(res) = num.checked_mul(n - i) {
463 res
464 } else {
465 return Err(Overflow(None))
466 };
467 den = if let Some(res) = den.checked_mul(i + 1) {
468 res
469 } else {
470 return Err(Overflow(None))
471 };
472 }];
473 Ok(Int(num / den))
474 }
475
476 /// Combinations of `n` items taken `r` at a time with repetitions, unordered.
477 ///
478 /// Also known as *multichoose*.
479 ///
480 /// # Formula
481 #[doc = FORMULA_COMBINE_REP!()]
482 ///
483 /// # Errors
484 /// Returns [`Overflow`] if the result cant't fit the type.
485 ///
486 /// # Examples
487 /// ```
488 /// # use devela::Int;
489 #[doc = "assert_eq![Ok(Int(10)), Int(3_" $t ").combine_rep(3)];"]
490 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").combine_rep(2)];"]
491 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").combine_rep(1)];"]
492 #[doc = "assert![Int(" $t "::MAX).combine_rep(" $t "::MAX).is_err()];"]
493 /// ```
494 pub const fn combine_rep(self, r: $t) -> Result<Int<$t>> {
495 let [n, mut num, mut den] = [self.0, 1, 1];
496 cfor![i in 0..r => {
497 let Some(factor) = n.checked_add(r - 1 - i) else {
498 return Err(Overflow(None))
499 };
500 num = if let Some(res) = num.checked_mul(factor) {
501 res
502 } else {
503 return Err(Overflow(None))
504 };
505 den = if let Some(res) = den.checked_mul(i + 1) {
506 res
507 } else {
508 return Err(Overflow(None))
509 };
510 }];
511 Ok(Int(num / den))
512 }
513
514 /// Permutations of `n` items taken `r` at a time, ordered.
515 ///
516 /// When $n=r$ or $n=r-1$ the result is the same as calculating the factorial $n!$.
517 ///
518 /// # Formula
519 #[doc = FORMULA_PERMUTE!()]
520 ///
521 /// # Errors
522 /// Returns [`MismatchedSizes`] if $r > n$ and
523 /// [`Overflow`] if the result cant't fit the type.
524 ///
525 /// # Examples
526 /// ```
527 /// # use devela::Int;
528 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").permute(3)];"]
529 #[doc = "assert_eq![Ok(Int(6)), Int(3_" $t ").permute(2)];"]
530 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").permute(1)];"]
531 #[doc = "assert![Int(3_" $t ").permute(4_" $t ").is_err()];"]
532 #[doc = "assert![Int(" $t "::MAX).permute(" $t "::MAX).is_err()];"]
533 /// ```
534 pub const fn permute(self, r: $t) -> Result<Int<$t>> {
535 let n = self.0;
536 iif![r > n; return Err(MismatchedSizes)];
537 let mut result: $t = 1;
538 cfor![i in 0..r => {
539 result = if let Some(res) = result.checked_mul(n - i) {
540 res
541 } else {
542 return Err(Overflow(None))
543 }
544 }];
545 Ok(Int(result))
546 }
547
548 /// Permutations of `n` items taken `r` at a time with repetitions, ordered.
549 ///
550 /// # Formula
551 #[doc = FORMULA_PERMUTE_REP!()]
552 ///
553 /// # Errors
554 /// Returns [`Overflow`] if the result cant't fit the type.
555 ///
556 /// # Examples
557 /// ```
558 /// # use devela::Int;
559 #[doc = "assert_eq![Ok(Int(27)), Int(3_" $t ").permute_rep(3)];"]
560 #[doc = "assert_eq![Ok(Int(9)), Int(3_" $t ").permute_rep(2)];"]
561 #[doc = "assert_eq![Ok(Int(3)), Int(3_" $t ").permute_rep(1)];"]
562 #[doc = "assert![Int(" $t "::MAX).permute_rep(" $t "::MAX).is_err()];"]
563 /// ```
564 #[cfg(feature = "cast")]
565 #[cfg_attr(feature = "nightly_doc", doc(cfg(feature = "cast")))]
566 pub const fn permute_rep(self, r: $t) -> Result<Int<$t>> {
567 let n = self.0;
568 let Ok(r_u32) = Cast(r).checked_cast_to_u32() else {
569 return Err(Overflow(None));
570 };
571 if let Some(res) = n.checked_pow(r_u32) {
572 Ok(Int(res))
573 } else {
574 Err(Overflow(None))
575 }
576 }
577 }
578 }};
579}
580impl_combinatorics!();