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//! [`half_permutations`]
13//!
14//! Like `permuations`, but skip any permutation which is lexically reversed from an earlier
15//! callback.  Only half the permutations are visited in total.
16//! Uses [Steinhaus-Johnson-Trotter's algorithm](https://en.wikipedia.org/wiki/Steinhaus%E2%80%93Johnson%E2%80%93Trotter_algorithm),
17//! modifying the slice in place.
18//!
19//! [`permutations`]: SliceOps::permutations
20//! [`half_permutations`]: SliceOps::half_permutations
21pub trait SliceOps<T> {
22    fn permutations(self, callback: impl FnMut(&[T]));
23    fn half_permutations(self, callback: impl FnMut(&[T]));
24}
25
26impl<T> SliceOps<T> for &mut [T] {
27    fn permutations(self, mut callback: impl FnMut(&[T])) {
28        callback(self);
29
30        let n = self.len();
31        let mut c = vec![0; n];
32        let mut i = 1;
33
34        while i < n {
35            if c[i] < i {
36                let swap_index = if i.is_multiple_of(2) { 0 } else { c[i] };
37                self.swap(swap_index, i);
38                callback(self);
39                c[i] += 1;
40                i = 1;
41            } else {
42                c[i] = 0;
43                i += 1;
44            }
45        }
46    }
47
48    fn half_permutations(self, mut callback: impl FnMut(&[T])) {
49        let n = self.len();
50        // Compute n!/2, the number of iterations we need.
51        let limit = (1..n + 1).product::<usize>() / 2;
52
53        // Track how far each element has moved from its original position
54        let mut pos = vec![0_usize; n];
55
56        // Track which direction an element needs to move next (-1 or 1)
57        let mut dir = vec![1_isize; n];
58
59        for _ in 0..limit {
60            callback(self);
61
62            // Each iteration requires scanning up to n positions to locate a candidate to swap
63            // with its neighbor, by moving left and right towards one another and updating pos and
64            // dir along the way.
65            let mut left = 0;
66            let mut right = n - 1;
67
68            loop {
69                pos[right] = pos[right].wrapping_add_signed(dir[right]);
70                if right + 1 == pos[right] {
71                    dir[right] = -1;
72                    if right > 1 {
73                        right -= 1;
74                    } else {
75                        self.swap(left, left + 1);
76                        break;
77                    }
78                } else if pos[right] == 0 {
79                    dir[right] = 1;
80                    left += 1;
81                    if right > 1 {
82                        right -= 1;
83                    } else {
84                        self.swap(left, left + 1);
85                        break;
86                    }
87                } else {
88                    let index = left + pos[right] - 1;
89                    self.swap(index, index + 1);
90                    break;
91                }
92            }
93        }
94    }
95}
aoc/util/slice.rs

aoc/util/
slice.rs
