sudoku_solver/utils/
combination_generator2.rs

1use std::sync::{Arc, LazyLock};
2
3use arrayvec::ArrayVec;
4use itertools::Itertools;
5
6const MAX_ARRAY_LEN: usize = 9;
7const MAX_SIZE: usize = 4;
8
9static CACHE: LazyLock<Vec<Vec<Arc<Vec<Vec<usize>>>>>> = LazyLock::new(|| {
10    (0..=MAX_ARRAY_LEN)
11        .map(|length| {
12            (0..=length.min(MAX_SIZE))
13                .map(|size| Arc::new((0..length).combinations(size).collect_vec()))
14                .collect_vec()
15        })
16        .collect_vec()
17});
18
19pub fn combinations<'a, T: Copy>(arr: &'a [T], size: usize) -> CombinationIterator<'a, T> {
20    debug_assert!(arr.len() <= MAX_ARRAY_LEN);
21    debug_assert!(size <= MAX_SIZE);
22
23    if arr.len() < size {
24        return CombinationIterator {
25            combination_cache: CACHE[0][0].clone(),
26            arr,
27            idx: usize::MAX,
28        };
29    }
30
31    let combination_cache = CACHE[arr.len()][size].clone();
32    CombinationIterator {
33        combination_cache,
34        arr,
35        idx: 0,
36    }
37}
38
39pub struct CombinationIterator<'a, T> {
40    combination_cache: Arc<Vec<Vec<usize>>>,
41    arr: &'a [T],
42    idx: usize,
43}
44
45impl<'a, T: Copy> Iterator for CombinationIterator<'a, T> {
46    type Item = ArrayVec<T, MAX_SIZE>;
47
48    fn size_hint(&self) -> (usize, Option<usize>) {
49        let len = self.combination_cache.len() - self.idx;
50        (len, Some(len))
51    }
52
53    fn next(&mut self) -> Option<Self::Item> {
54        if self.idx >= self.combination_cache.len() {
55            return None;
56        }
57        let mut combination = ArrayVec::new();
58        for &element in &self.combination_cache[self.idx] {
59            combination.push(self.arr[element]);
60        }
61        self.idx += 1;
62        Some(combination)
63    }
64}
65
66#[cfg(test)]
67mod tests {
68    use super::*;
69
70    #[test]
71    fn test_combination_generator() {
72        for len in 0..=MAX_ARRAY_LEN {
73            for size in 0..=MAX_SIZE {
74                let arr: Vec<u8> = (0..len as u8).collect();
75                let combinations: Vec<ArrayVec<u8, MAX_SIZE>> = combinations(&arr, size).collect();
76                let expected: Vec<Vec<u8>> = arr.iter().copied().combinations(size).collect();
77                assert_eq!(combinations.len(), expected.len());
78                for (combination, expected) in combinations.iter().zip(expected.iter()) {
79                    assert_eq!(combination.as_slice(), expected.as_slice());
80                }
81            }
82        }
83    }
84}
sudoku_solver/utils/combination_generator2.rs

sudoku_solver/utils/
combination_generator2.rs
