1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105

/// next permutation です。
///
/// [実装の参考資料](https://ngtkana.hatenablog.com/entry/2021/11/08/000209)
pub trait NextPermutation {
    fn next_permutation(&mut self) -> bool;
}

impl<T: Ord> NextPermutation for [T] {
    /// 数列を辞書順でひとつ進めます。進めなかったら false を返します。
    ///
    /// # Examples
    /// ```
    /// use next_permutation::NextPermutation;
    /// let mut a = vec![1, 2, 3];
    /// a.next_permutation();
    /// assert_eq!(a, vec![1, 3, 2]);
    /// a.next_permutation();
    /// assert_eq!(a, vec![2, 1, 3]);
    /// let mut a = vec![3, 2, 1];
    /// assert!(!a.next_permutation());
    /// ```
    fn next_permutation(&mut self) -> bool {
        if self.len() <= 1 {
            return false;
        }
        let mut i = self.len() - 1;
        while i > 0 && self[i - 1] >= self[i] {
            i -= 1;
        }
        if i == 0 {
            return false;
        }
        let mut j = self.len() - 1;
        while self[i - 1] >= self[j] {
            j -= 1;
        }
        self.swap(i - 1, j);
        self[i..].reverse();
        true
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn empty_test() {
        let mut a: Vec<i32> = vec![];
        assert!(!a.next_permutation());
    }

    #[test]
    fn one_test() {
        let mut a = vec![1];
        assert!(!a.next_permutation());
    }

    #[test]
    fn uniq_test() {
        let mut a = vec![1, 2, 3];
        let want = vec![
            vec![1, 2, 3],
            vec![1, 3, 2],
            vec![2, 1, 3],
            vec![2, 3, 1],
            vec![3, 1, 2],
            vec![3, 2, 1],
        ];
        for i in 0..want.len() {
            assert_eq!(a, want[i]);
            if i < want.len() - 1 {
                assert_eq!(a.next_permutation(), true);
            } else {
                assert_eq!(a.next_permutation(), false);
            }
        }
    }
    #[test]
    fn general_test() {
        let mut a = vec![1, 2, 2, 3];
        let want = vec![
            vec![1, 2, 2, 3],
            vec![1, 2, 3, 2],
            vec![1, 3, 2, 2],
            vec![2, 1, 2, 3],
            vec![2, 1, 3, 2],
            vec![2, 2, 1, 3],
            vec![2, 2, 3, 1],
            vec![2, 3, 1, 2],
            vec![2, 3, 2, 1],
            vec![3, 1, 2, 2],
            vec![3, 2, 1, 2],
            vec![3, 2, 2, 1],
        ];
        for i in 0..want.len() {
            assert_eq!(a, want[i]);
            if i < want.len() - 1 {
                assert_eq!(a.next_permutation(), true);
            } else {
                assert_eq!(a.next_permutation(), false);
            }
        }
    }
}