permutations_iter/
lib.rs

1//! Generate permutations iteratively without recursion.
2//!
3//! ``Permutations.of(n)`` function generates an iterator instance for permutations of `0..n`.
4//!
5//! ``Permutations.next()`` uses Steinhaus-Johnson-Trotter algorithm with Even's modification to generate the next permutation
6//! in $O(n)$ time.
7//!
8//! Each iterator is one-way. You need to construct a new one for iterating again.
9
10/// Generates the inverse permutation. Has $O(n)$ time complexity.
11pub fn inverse_perm(perm: &Vec<usize>) -> Vec<usize> {
12    let mut rev_perm = perm.clone();
13    for (ii, i) in perm.iter().enumerate() {
14        rev_perm[*i] = ii;
15    }
16    rev_perm
17}
18
19/// Implements ``Iterator``.
20pub struct Permutations {
21    n: usize,
22    perm: Vec<usize>,
23    direction: Vec<i8>,
24    is_initiated: bool,
25    is_finished: bool,
26}
27
28impl Permutations {
29    /// n must be greater than 0!
30    pub fn of(n: usize) -> Permutations {
31        assert!(n > 0);
32        Permutations {
33            n,
34            perm: vec![0; n],
35            direction: vec![0; n],
36            is_initiated: false,
37            is_finished: false,
38        }
39    }
40
41    pub fn get_n(&self) -> usize {
42        self.n
43    }
44}
45
46impl Iterator for Permutations {
47    type Item = Vec<usize>;
48
49    fn next(&mut self) -> Option<Self::Item> {
50        if !self.is_initiated {
51            for i in 1..self.n {
52                self.perm[i] = i;
53                self.direction[i] = -1;
54            }
55            self.is_initiated = true;
56            return Some(self.perm.clone());
57        }
58        if self.is_finished {
59            return None;
60        }
61        // We know we have a valid perm & direction here, but we may be finished.
62        let rev_perm = inverse_perm(&self.perm);
63        // Find largest element i that has non-zero direction
64        let mut i = self.n;
65        let mut ii = 0;
66        let mut id = 0;
67        for j in (0..self.n).rev() {
68            ii = rev_perm[j];
69            id = self.direction[ii];
70            if id != 0 {
71                i = j;
72                break;
73            }
74        }
75        if i == self.n {
76            self.is_finished = true;
77            return None;
78        }
79        // Swap i along direction i
80        let ii_new = (ii as isize + id as isize) as usize;
81        self.perm.swap(ii, ii_new);
82        self.direction.swap(ii, ii_new);
83        // Update directions
84        if ii_new == 0
85            || ii_new == self.n - 1
86            || self.perm[(ii_new as isize + id as isize) as usize] > i
87        {
88            self.direction[ii_new] = 0;
89        }
90        for j in (i + 1)..self.n {
91            let ji = rev_perm[j];
92            self.direction[ji] = if ji < ii_new { 1 } else { -1 };
93        }
94        Some(self.perm.clone())
95    }
96}
97
98#[cfg(test)]
99mod tests {
100    use crate::Permutations;
101
102    /// Prints permutations of 4
103    #[test]
104    fn print_permutations_of_4() {
105        println!("All permutations of [4]");
106        for perm in Permutations::of(4) {
107            println!("{:?}", perm);
108        }
109    }
110
111    /// Prints first 50 permutations of 20
112    #[test]
113    fn print_first_50_permutations_of_20() {
114        println!("First 50 permutations of [20]");
115        for perm in Permutations::of(20).take(50) {
116            println!("{:?}", perm);
117        }
118    }
119}
permutations_iter/lib.rs

permutations_iter/
lib.rs
