aoc/util/slice.rs
1//! Extension methods for slices.
2//!
3//! # Methods
4//!
5//! [`permutations`]
6//!
7//! Generates all possible permutations of a mutable slice, passing them one at a time to a
8//! callback function.
9//! Uses [Heap's algorithm](https://en.wikipedia.org/wiki/Heap%27s_algorithm) for efficiency,
10//! modifying the slice in place.
11//!
12//! [`fold_decimal`]
13//!
14//! Accumulates a slice of digits from 0 to 9 inclusive into a single integer.
15//!
16//! [`permutations`]: SliceOps::permutations
17//! [`fold_decimal`]: SliceOps2::fold_decimal
18use super::integer::*;
19
20pub trait SliceOps<T> {
21 fn permutations(self, callback: impl FnMut(&[T]));
22}
23
24impl<T> SliceOps<T> for &mut [T] {
25 fn permutations(self, mut callback: impl FnMut(&[T])) {
26 callback(self);
27
28 let n = self.len();
29 let mut c = vec![0; n];
30 let mut i = 1;
31
32 while i < n {
33 if c[i] < i {
34 let swap_index = if i.is_multiple_of(2) { 0 } else { c[i] };
35 self.swap(swap_index, i);
36 callback(self);
37 c[i] += 1;
38 i = 1;
39 } else {
40 c[i] = 0;
41 i += 1;
42 }
43 }
44 }
45}
46
47pub trait SliceOps2<T: Integer<T>> {
48 /// Folds a slice of digits into an integer.
49 fn fold_decimal(self) -> T;
50}
51
52impl<T: Integer<T>> SliceOps2<T> for &[T] {
53 #[inline]
54 fn fold_decimal(self) -> T {
55 self.iter().fold(T::ZERO, |acc, &b| T::TEN * acc + b)
56 }
57}