next_permutation/
lib.rs

1/// next permutation です。
2///
3/// [実装の参考資料](https://ngtkana.hatenablog.com/entry/2021/11/08/000209)
4pub trait NextPermutation {
5    fn next_permutation(&mut self) -> bool;
6}
7
8impl<T: Ord> NextPermutation for [T] {
9    /// 数列を辞書順でひとつ進めます。進めなかったら false を返します。
10    ///
11    /// # Examples
12    /// ```
13    /// use next_permutation::NextPermutation;
14    /// let mut a = vec![1, 2, 3];
15    /// a.next_permutation();
16    /// assert_eq!(a, vec![1, 3, 2]);
17    /// a.next_permutation();
18    /// assert_eq!(a, vec![2, 1, 3]);
19    /// let mut a = vec![3, 2, 1];
20    /// assert!(!a.next_permutation());
21    /// ```
22    fn next_permutation(&mut self) -> bool {
23        if self.len() <= 1 {
24            return false;
25        }
26        let mut i = self.len() - 1;
27        while i > 0 && self[i - 1] >= self[i] {
28            i -= 1;
29        }
30        if i == 0 {
31            return false;
32        }
33        let mut j = self.len() - 1;
34        while self[i - 1] >= self[j] {
35            j -= 1;
36        }
37        self.swap(i - 1, j);
38        self[i..].reverse();
39        true
40    }
41}
42
43#[cfg(test)]
44mod tests {
45    use super::*;
46
47    #[test]
48    fn empty_test() {
49        let mut a: Vec<i32> = vec![];
50        assert!(!a.next_permutation());
51    }
52
53    #[test]
54    fn one_test() {
55        let mut a = vec![1];
56        assert!(!a.next_permutation());
57    }
58
59    #[test]
60    fn uniq_test() {
61        let mut a = vec![1, 2, 3];
62        let want = vec![
63            vec![1, 2, 3],
64            vec![1, 3, 2],
65            vec![2, 1, 3],
66            vec![2, 3, 1],
67            vec![3, 1, 2],
68            vec![3, 2, 1],
69        ];
70        for i in 0..want.len() {
71            assert_eq!(a, want[i]);
72            if i < want.len() - 1 {
73                assert_eq!(a.next_permutation(), true);
74            } else {
75                assert_eq!(a.next_permutation(), false);
76            }
77        }
78    }
79    #[test]
80    fn general_test() {
81        let mut a = vec![1, 2, 2, 3];
82        let want = vec![
83            vec![1, 2, 2, 3],
84            vec![1, 2, 3, 2],
85            vec![1, 3, 2, 2],
86            vec![2, 1, 2, 3],
87            vec![2, 1, 3, 2],
88            vec![2, 2, 1, 3],
89            vec![2, 2, 3, 1],
90            vec![2, 3, 1, 2],
91            vec![2, 3, 2, 1],
92            vec![3, 1, 2, 2],
93            vec![3, 2, 1, 2],
94            vec![3, 2, 2, 1],
95        ];
96        for i in 0..want.len() {
97            assert_eq!(a, want[i]);
98            if i < want.len() - 1 {
99                assert_eq!(a.next_permutation(), true);
100            } else {
101                assert_eq!(a.next_permutation(), false);
102            }
103        }
104    }
105}