algorithms_edu/algo/misc/
permutations.rs

1pub struct Permutations<T: Ord> {
2    data: Vec<T>,
3    first: bool,
4}
5
6impl<T: Ord> Iterator for Permutations<T> {
7    type Item = *const [T];
8    /// Generates the next ordered permutation in-place (skips repeated permutations).
9    /// Calling this when the vec is already at the highest permutation returns `None`.
10    fn next(&mut self) -> Option<Self::Item> {
11        if self.first {
12            self.first = false;
13            Some(&self.data[..])
14        } else {
15            self.get_first().map(|mut first| {
16                let mut to_swap = self.data.len() - 1;
17                while self.data[first] >= self.data[to_swap] {
18                    to_swap -= 1;
19                }
20                self.data.swap(first, to_swap);
21                first += 1;
22                to_swap = self.data.len() - 1;
23                while first < to_swap {
24                    self.data.swap(first, to_swap);
25                    first += 1;
26                    to_swap -= 1;
27                }
28                &self.data[..] as *const [T]
29            })
30        }
31    }
32}
33
34impl<T: Ord> Permutations<T> {
35    pub fn new(data: Vec<T>) -> Self {
36        Self { data, first: true }
37    }
38    fn get_first(&self) -> Option<usize> {
39        for i in (0..self.data.len() - 1).rev() {
40            if self.data[i] < self.data[i + 1] {
41                return Some(i);
42            }
43        }
44        None
45    }
46}
47
48pub trait IntoPermutations<T: Ord> {
49    fn permutations(self) -> Permutations<T>;
50}
51
52impl<T: Ord> IntoPermutations<T> for Vec<T> {
53    fn permutations(self) -> Permutations<T> {
54        Permutations::new(self)
55    }
56}
57
58#[cfg(test)]
59mod tests {
60    use super::*;
61    use crate::algo::math::factorial::Factorial;
62    #[test]
63    fn test_permutations() {
64        for perm in vec![1, 2, 3, 4, 5].permutations() {
65            println!("{:?}", unsafe { &*perm });
66        }
67        assert_eq!(vec![1, 2, 3, 4, 5].permutations().count(), 5.factorial());
68    }
69}
algorithms_edu/algo/misc/permutations.rs

algorithms_edu/algo/misc/
permutations.rs
