nekolib/algo/
permutation.rs

1//! 順列。
2
3/// 辞書順で次の順列の生成。
4///
5/// # Idea
6/// `todo!()`
7///
8/// # References
9/// - <https://stackoverflow.com/questions/11483060>
10///
11/// # Examples
12/// ```
13/// use nekolib::algo::next_permutation;
14///
15/// let mut a = vec![1, 3, 2];
16/// assert!(next_permutation(&mut a));
17/// assert_eq!(a, [2, 1, 3]);
18///
19/// // last one
20/// let mut a = vec![3, 2];
21/// assert!(!next_permutation(&mut a));
22/// assert_eq!(a, [2, 3]);
23///
24/// // empty one
25/// let mut a = Vec::<()>::new();
26/// assert!(!next_permutation(&mut a));
27///
28/// // duplicated one
29/// let mut a = vec![1, 3, 2, 2, 3];
30/// next_permutation(&mut a);
31/// assert_eq!(a, [1, 3, 2, 3, 2]);
32pub fn next_permutation<T: Ord>(a: &mut [T]) -> bool {
33    let n = a.len();
34    if n <= 1 {
35        return false;
36    }
37
38    for i in (0..n - 1).rev() {
39        if a[i] < a[i + 1] {
40            let j = (0..n).rev().find(|&j| a[i] < a[j]).unwrap();
41            a.swap(i, j);
42            a[i + 1..].reverse();
43            return true;
44        }
45    }
46
47    a.reverse();
48    false
49}
50
51pub fn prev_permutation<T: Ord>(a: &mut [T]) -> bool {
52    let n = a.len();
53    if n <= 1 {
54        return false;
55    }
56
57    for i in (0..n - 1).rev() {
58        if a[i] > a[i + 1] {
59            let j = (0..n).rev().find(|&j| a[i] > a[j]).unwrap();
60            a.swap(i, j);
61            a[i + 1..].reverse();
62            return true;
63        }
64    }
65
66    a.reverse();
67    false
68}
69
70fn next_permutation_with_count<T: Ord>(a: &mut [T], k: usize) -> bool {
71    // precondition: k <= a.len(), and a[k..] is sorted
72    // postcondition: a[k..] is sorted
73
74    let n = a.len();
75    for i in (0..k).rev() {
76        let j = if k < n && a[i] < a[n - 1] {
77            (k..).find(|&j| a[i] < a[j]).unwrap()
78        } else if i + 1 < n && a[i] < a[i + 1] {
79            (i..k).rev().find(|&j| a[i] < a[j]).unwrap()
80        } else {
81            continue;
82        };
83        a.swap(i, j);
84        a[i + 1..k].reverse();
85        a[i + 1..].rotate_right(n - k);
86        return true;
87    }
88    false
89}
90
91fn prev_permutation_with_count<T: Ord>(a: &mut [T], k: usize) -> bool {
92    // precondition: k <= a.len(), and a[k..] is reversely sorted
93    // postcondition: a[k..] is reversely sorted
94
95    let n = a.len();
96    for i in (0..k).rev() {
97        let j = if k < n && a[i] > a[n - 1] {
98            (k..).find(|&j| a[i] > a[j]).unwrap()
99        } else if i + 1 < n && a[i] > a[i + 1] {
100            (i..k).rev().find(|&j| a[i] > a[j]).unwrap()
101        } else {
102            continue;
103        };
104        a.swap(i, j);
105        a[i + 1..k].reverse();
106        a[i + 1..].rotate_right(n - k);
107        return true;
108    }
109    false
110}
111
112pub struct Permutations<T>(Vec<T>);
113
114impl<T: Ord> From<Vec<T>> for Permutations<T> {
115    fn from(buf: Vec<T>) -> Self { Self(buf) }
116}
117
118impl<T: Ord> Permutations<T> {
119    pub fn next(&mut self) -> bool { next_permutation(&mut self.0) }
120    pub fn prev(&mut self) -> bool { prev_permutation(&mut self.0) }
121    pub fn peek(&self) -> &[T] { &self.0 }
122}
123
124impl<T: Ord + Clone> Permutations<T> {
125    pub fn forward(self, count: usize) -> Forward<T> {
126        Forward::new(self, count)
127    }
128    pub fn backward(self, count: usize) -> Backward<T> {
129        Backward::new(self, count)
130    }
131}
132
133pub struct Forward<T> {
134    buf: Vec<T>,
135    count: usize,
136    finish: bool,
137}
138
139impl<T: Clone + Ord> Forward<T> {
140    fn new(perm: Permutations<T>, count: usize) -> Self {
141        let mut buf = perm.0;
142        buf[count..].sort();
143        Self { buf, count, finish: false }
144    }
145}
146
147impl<T: Clone + Ord> Iterator for Forward<T> {
148    type Item = Vec<T>;
149    fn next(&mut self) -> Option<Self::Item> {
150        if self.finish {
151            None
152        } else {
153            let tmp = self.buf[..self.count].to_vec();
154            self.finish =
155                !next_permutation_with_count(&mut self.buf, self.count);
156            Some(tmp)
157        }
158    }
159}
160
161pub struct Backward<T> {
162    buf: Vec<T>,
163    count: usize,
164    finish: bool,
165}
166
167impl<T: Clone + Ord> Backward<T> {
168    fn new(perm: Permutations<T>, count: usize) -> Self {
169        let mut buf = perm.0;
170        buf[count..].sort_by(|x, y| y.cmp(x));
171        Self { buf, count, finish: false }
172    }
173}
174
175impl<T: Clone + Ord> Iterator for Backward<T> {
176    type Item = Vec<T>;
177    fn next(&mut self) -> Option<Self::Item> {
178        if self.finish {
179            None
180        } else {
181            let tmp = self.buf[..self.count].to_vec();
182            self.finish =
183                !prev_permutation_with_count(&mut self.buf, self.count);
184            Some(tmp)
185        }
186    }
187}
188
189#[test]
190fn iter() {
191    let expected = vec![
192        vec![0, 1, 1, 2, 2],
193        vec![0, 1, 2, 1, 2],
194        vec![0, 1, 2, 2, 1],
195        vec![0, 2, 1, 1, 2],
196        vec![0, 2, 1, 2, 1],
197        vec![0, 2, 2, 1, 1],
198        vec![1, 0, 1, 2, 2],
199        vec![1, 0, 2, 1, 2],
200        vec![1, 0, 2, 2, 1],
201        vec![1, 1, 0, 2, 2],
202        vec![1, 1, 2, 0, 2],
203        vec![1, 1, 2, 2, 0],
204        vec![1, 2, 0, 1, 2],
205        vec![1, 2, 0, 2, 1],
206        vec![1, 2, 1, 0, 2],
207        vec![1, 2, 1, 2, 0],
208        vec![1, 2, 2, 0, 1],
209        vec![1, 2, 2, 1, 0],
210        vec![2, 0, 1, 1, 2],
211        vec![2, 0, 1, 2, 1],
212        vec![2, 0, 2, 1, 1],
213        vec![2, 1, 0, 1, 2],
214        vec![2, 1, 0, 2, 1],
215        vec![2, 1, 1, 0, 2],
216        vec![2, 1, 1, 2, 0],
217        vec![2, 1, 2, 0, 1],
218        vec![2, 1, 2, 1, 0],
219        vec![2, 2, 0, 1, 1],
220        vec![2, 2, 1, 0, 1],
221        vec![2, 2, 1, 1, 0],
222    ];
223
224    let fwd = Permutations::from(expected[0].clone()).forward(5);
225    assert!(fwd.eq(expected.iter().cloned()));
226
227    let fwd_1 = Permutations::from(expected[1].clone()).forward(5);
228    assert!(fwd_1.eq(expected[1..].iter().cloned()));
229
230    let fwd_28 = Permutations::from(expected[28].clone()).forward(5);
231    assert!(fwd_28.eq(expected[28..].iter().cloned()));
232
233    let fwd_29 = Permutations::from(expected[29].clone()).forward(5);
234    assert!(fwd_29.eq(expected[29..].iter().cloned()));
235
236    let bwd = Permutations::from(expected[0].clone()).backward(5);
237    assert!(bwd.eq(expected[..=0].iter().rev().cloned()));
238
239    let bwd_1 = Permutations::from(expected[1].clone()).backward(5);
240    assert!(bwd_1.eq(expected[..=1].iter().rev().cloned()));
241
242    let bwd_28 = Permutations::from(expected[28].clone()).backward(5);
243    assert!(bwd_28.eq(expected[..=28].iter().rev().cloned()));
244
245    let bwd_29 = Permutations::from(expected[29].clone()).backward(5);
246    assert!(bwd_29.eq(expected[..=29].iter().rev().cloned()));
247}
248
249#[test]
250fn empty() {
251    let empty: Vec<()> = vec![];
252    let fwd = Permutations::from(empty.clone()).forward(0);
253    assert!(fwd.eq(Some(vec![])));
254    let bwd = Permutations::from(empty.clone()).backward(0);
255    assert!(bwd.eq(Some(vec![])));
256}
257
258#[test]
259fn single() {
260    let empty = vec![()];
261    let fwd = Permutations::from(empty.clone()).forward(1);
262    assert!(fwd.eq(Some(vec![()])));
263    let bwd = Permutations::from(empty.clone()).backward(1);
264    assert!(bwd.eq(Some(vec![()])));
265}
266
267#[cfg(test)]
268fn is_sorted<T: Ord>(a: &[T]) -> bool { a.windows(2).all(|w| w[0] <= w[1]) }
269
270#[test]
271fn partial_fwd() {
272    for n in 1..=8 {
273        for k in 1..=n {
274            let a: Vec<_> = (0..n).collect();
275            let expected: Vec<_> = Permutations::from(a.clone())
276                .forward(n)
277                .filter(|p| is_sorted(&p[k..]))
278                .map(|p| p[..k].to_vec())
279                .collect();
280
281            assert!(Permutations::from(a).forward(k).eq(expected));
282        }
283    }
284}
285
286#[test]
287fn partial_bwd() {
288    for n in 1..=8 {
289        for k in 1..=n {
290            let a: Vec<_> = (0..n).collect();
291            let expected: Vec<_> = Permutations::from(a.clone())
292                .forward(n)
293                .filter(|p| is_sorted(&p[k..]))
294                .map(|p| p[..k].to_vec())
295                .collect();
296            let expected: Vec<_> = expected.into_iter().rev().collect();
297
298            let a_rev: Vec<_> = a.into_iter().rev().collect();
299            assert!(Permutations::from(a_rev).backward(k).eq(expected));
300        }
301    }
302}
303
304#[test]
305fn partial_dup() {
306    let a = vec![0, 1, 1, 2, 2, 3, 3, 3];
307    for n in 1..=8 {
308        for k in 1..=n {
309            let a: Vec<_> = a[..n].to_vec();
310            let expected: Vec<_> = Permutations::from(a.clone())
311                .forward(n)
312                .filter(|p| is_sorted(&p[k..]))
313                .map(|p| p[..k].to_vec())
314                .collect();
315
316            assert!(Permutations::from(a).forward(k).eq(expected));
317        }
318    }
319}
nekolib/algo/permutation.rs

nekolib/algo/
permutation.rs
