1pub trait NextPermutation {
5 fn next_permutation(&mut self) -> bool;
6}
7
8impl<T: Ord> NextPermutation for [T] {
9 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}