competitive_programming_rs/math/
next_permutation.rs

1pub trait NextPermutation {
2    fn next_permutation(&mut self) -> bool;
3}
4
5impl<T> NextPermutation for [T]
6where
7    T: PartialOrd,
8{
9    fn next_permutation(&mut self) -> bool {
10        if self.len() < 2 {
11            return false;
12        }
13
14        let mut i = self.len() - 1;
15        while i > 0 && self[i - 1] >= self[i] {
16            i -= 1;
17        }
18
19        if i == 0 {
20            return false;
21        }
22
23        let mut j = self.len() - 1;
24        while j >= i && self[j] <= self[i - 1] {
25            j -= 1;
26        }
27
28        self.swap(j, i - 1);
29        self[i..].reverse();
30        true
31    }
32}
33
34#[cfg(test)]
35mod tests {
36    use super::NextPermutation;
37    use std::collections::BTreeSet;
38
39    #[test]
40    fn test_next_permutation() {
41        let mut x = vec![1, 2, 3, 4, 5];
42        let mut set = BTreeSet::new();
43        let mut count = 0;
44        while x.next_permutation() {
45            count += 1;
46            set.insert(x.clone());
47        }
48        assert_eq!(count + 1, 5 * 4 * 3 * 2);
49        assert_eq!(set.len(), count);
50    }
51}

competitive_programming_rs/math/next_permutation.rs

competitive_programming_rs/math/
next_permutation.rs