osom_lib_numbers/iterators/
const_permutation.rs

1/// A generator for permutations of `N` elements.
2#[must_use]
3pub struct ConstPermutationGenerator<const N: usize> {
4    current: [usize; N],
5    first: bool,
6    done: bool,
7}
8
9impl<const N: usize> ConstPermutationGenerator<N> {
10    /// The length of the permutations.
11    #[inline(always)]
12    #[must_use]
13    pub const fn length(&self) -> usize {
14        N
15    }
16
17    /// Creates a new [`ConstPermutationGenerator`].
18    pub const fn new() -> Self {
19        let mut current = [0; N];
20        let mut i = 0;
21        while i < N {
22            current[i] = i;
23            i += 1;
24        }
25        Self {
26            current,
27            first: true,
28            done: false,
29        }
30    }
31
32    /// Returns the next permutation.
33    #[must_use]
34    pub const fn next(&mut self) -> Option<[usize; N]> {
35        if self.done {
36            return None;
37        }
38
39        if self.first {
40            self.first = false;
41            return Some(self.current);
42        }
43
44        if Self::next_permutation(&mut self.current) {
45            Some(self.current)
46        } else {
47            self.done = true;
48            None
49        }
50    }
51
52    const fn next_permutation(data: &mut [usize; N]) -> bool {
53        if N < 2 {
54            return false;
55        }
56
57        // Find rightmost ascent
58        let mut i = N - 2;
59        loop {
60            if data[i] < data[i + 1] {
61                break;
62            }
63            if i == 0 {
64                return false;
65            }
66            i -= 1;
67        }
68
69        // Find smallest larger element to the right
70        let mut j = data.len() - 1;
71        while data[j] <= data[i] {
72            j -= 1;
73        }
74
75        data.swap(i, j);
76
77        let slice = unsafe { core::slice::from_raw_parts_mut(data.as_mut_ptr().add(i + 1), N - i - 1) };
78        slice.reverse();
79
80        true
81    }
82}
83
84impl<const N: usize> Default for ConstPermutationGenerator<N> {
85    fn default() -> Self {
86        Self::new()
87    }
88}
89
90impl<const N: usize> Clone for ConstPermutationGenerator<N> {
91    fn clone(&self) -> Self {
92        Self {
93            current: self.current,
94            first: self.first,
95            done: self.done,
96        }
97    }
98}
99
100impl<const N: usize> Iterator for ConstPermutationGenerator<N> {
101    type Item = [usize; N];
102    fn next(&mut self) -> Option<Self::Item> {
103        self.next()
104    }
105}
osom_lib_numbers/iterators/const_permutation.rs

osom_lib_numbers/iterators/
const_permutation.rs
