permutation_generator/single_permutation/
single_permutation_8.rs

1use bit_index::BitIndex8;
2
3use crate::factorial::factorial16;
4
5#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
6pub struct SinglePermutation8 {
7    elems:       BitIndex8,
8    next_mod:    u16,
9    current_idx: u16,
10}
11
12impl SinglePermutation8 {
13    #[must_use]
14    pub fn new_precalculated(nb_elems: u8, nb_perms: u16, idx: u16) -> Option<Self> {
15        if idx >= nb_perms {
16            None
17        } else {
18            Some(Self {
19                elems:       BitIndex8::new(nb_elems).unwrap(),
20                next_mod:    nb_perms / u16::from(nb_elems),
21                current_idx: idx,
22            })
23        }
24    }
25
26    #[must_use]
27    pub fn new(nb_elems: u8, idx: u16) -> Self {
28        Self::new_precalculated(nb_elems, factorial16(nb_elems), idx).unwrap()
29    }
30
31    #[inline]
32    #[must_use]
33    pub fn nb_remaining(&self) -> usize { self.elems.nb_elements() as usize }
34}
35
36impl Iterator for SinglePermutation8 {
37    type Item = u8;
38
39    #[allow(clippy::cast_possible_truncation)]
40    fn next(&mut self) -> Option<Self::Item> {
41        if self.elems.nb_elements() == 0 {
42            return None;
43        }
44        let bit_nb = self.current_idx / self.next_mod;
45        self.current_idx -= bit_nb * self.next_mod;
46        self.next_mod /= u16::from(self.elems.nb_elements()).saturating_sub(2) + 1;
47        self.elems.pop(bit_nb as u8)
48    }
49
50    fn size_hint(&self) -> (usize, Option<usize>) {
51        let nb_remaining = self.nb_remaining();
52        (nb_remaining, Some(nb_remaining))
53    }
54
55    fn count(self) -> usize { self.nb_remaining() }
56}
57
58#[cfg(test)]
59mod tests {
60    use crate::{SinglePermutation8, factorial::factorial16};
61
62    fn single_perm(nb_elems: u8, idx: u16) -> Option<SinglePermutation8> {
63        SinglePermutation8::new_precalculated(nb_elems, factorial16(nb_elems), idx)
64    }
65
66    #[test]
67    fn new() {
68        assert_eq!(None, single_perm(4, 24));
69    }
70
71    #[test]
72    fn new_unchecked_iterator() {
73        assert_eq!(&[0, 1, 2, 3], single_perm(4, 0).unwrap().collect::<Vec<_>>().as_slice());
74
75        assert_eq!(&[1, 0, 2, 3], single_perm(4, 6).unwrap().collect::<Vec<_>>().as_slice());
76
77        assert_eq!(&[2, 0, 1, 3], single_perm(4, 12).unwrap().collect::<Vec<_>>().as_slice());
78
79        assert_eq!(&[3, 0, 1, 2], single_perm(4, 18).unwrap().collect::<Vec<_>>().as_slice());
80
81        assert_eq!(&[3, 2, 1, 0], single_perm(4, 23).unwrap().collect::<Vec<_>>().as_slice());
82    }
83}
permutation_generator/single_permutation/single_permutation_8.rs

permutation_generator/single_permutation/
single_permutation_8.rs
