jabba_lib/
jpermutation.rs

1//! # permutation
2//!
3//! Generate the lexicographically next permutation of a sequence
4//! of elements.
5//!
6//! Pseudo-code:
7//!
8//! 1. Find the largest index `k` such that `a[k] < a[k + 1]`.
9//!    If no such index exists, the permutation is the last permutation.
10//! 2. Find the largest index `l` such that `a[k] < a[l]`.
11//!    Since `k + 1` is such an index, `l` is well-defined and satisfies `k < l`.
12//! 3. Swap `a[k]` with `a[l]`.
13//! 4. Reverse the sequence from `a[k + 1]` up to end including the final element.
14
15/// Generates the lexicographically next permutation of an array / vector.
16///
17/// Returns `false` if the permutation is the last permutation.
18///
19/// The sequence is modified in place.
20///
21/// # Examples
22///
23/// ```
24/// let mut v = ['a', 'b', 'c'];
25///
26/// jabba_lib::jpermutation::lexicographically_next_permutation(&mut v);
27/// assert_eq!(v, ['a', 'c', 'b']);
28/// jabba_lib::jpermutation::lexicographically_next_permutation(&mut v);
29/// assert_eq!(v, ['b', 'a', 'c']);
30/// jabba_lib::jpermutation::lexicographically_next_permutation(&mut v);
31/// assert_eq!(v, ['b', 'c', 'a']);
32pub fn lexicographically_next_permutation<T: PartialOrd + Copy>(a: &mut [T]) -> bool {
33    let mut i = a.len() - 2;
34    loop {
35        if a[i] < a[i + 1] {
36            break;
37        }
38        if i == 0 {
39            return false;
40        }
41        i -= 1;
42    }
43    // else, if a[i] < a[i + 1]
44    let mut j = a.len() - 1;
45    while !(a[j] > a[i]) {
46        j -= 1;
47    }
48    (a[i], a[j]) = (a[j], a[i]); // swap
49    reverse(a, i + 1, a.len() - 1); // reverse the elements from position i+1 until the end
50    true
51}
52
53/**********
54  private
55***********/
56
57fn reverse<T: Copy>(a: &mut [T], i: usize, j: usize) {
58    let mut i = i;
59    let mut j = j;
60    while i < j {
61        (a[i], a[j]) = (a[j], a[i]); // swap
62                                     //
63        i += 1;
64        j -= 1;
65    }
66}
67
68// ==========================================================================
69
70#[cfg(test)]
71mod tests {
72    use super::*;
73
74    use lexicographically_next_permutation as next_perm;
75
76    #[test]
77    fn lexicographically_next_permutation_test1() {
78        let mut v = ['a', 'b', 'c'];
79        next_perm(&mut v);
80        assert_eq!(v, ['a', 'c', 'b']);
81        next_perm(&mut v);
82        assert_eq!(v, ['b', 'a', 'c']);
83        next_perm(&mut v);
84        assert_eq!(v, ['b', 'c', 'a']);
85        next_perm(&mut v);
86        assert_eq!(v, ['c', 'a', 'b']);
87        next_perm(&mut v);
88        assert_eq!(v, ['c', 'b', 'a']);
89        let status = next_perm(&mut v);
90        assert_eq!(status, false);
91    }
92
93    #[test]
94    fn lexicographically_next_permutation_test2() {
95        let mut v = vec!['C', 'A', 'D', 'B'];
96        next_perm(&mut v);
97        assert_eq!(v, vec!['C', 'B', 'A', 'D']);
98        //
99        let mut v = [1, 2, 9, 6, 5];
100        next_perm(&mut v);
101        assert_eq!(v, [1, 5, 2, 6, 9]);
102    }
103}
jabba_lib/jpermutation.rs

jabba_lib/
jpermutation.rs
