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 106 107 108 109 110 111 112 113
/// Permute a slice into its next or previous permutation (in lexical order). /// /// ``` /// use permutohedron::LexicalPermutation; /// /// let mut data = [1, 2, 3]; /// let mut permutations = Vec::new(); /// /// loop { /// permutations.push(data.to_vec()); /// if !data.next_permutation() { /// break; /// } /// } /// /// assert_eq!(permutations, &[&[1, 2, 3], &[1, 3, 2], /// &[2, 1, 3], &[2, 3, 1], /// &[3, 1, 2], &[3, 2, 1]]); /// /// // `data` has been mutated in-place: /// assert_eq!(data, [3, 2, 1]); /// ``` pub trait LexicalPermutation { /// Return `true` if the slice was permuted, `false` if it is already /// at the last ordered permutation. fn next_permutation(&mut self) -> bool; /// Return `true` if the slice was permuted, `false` if it is already /// at the first ordered permutation. fn prev_permutation(&mut self) -> bool; } impl<T> LexicalPermutation for [T] where T: Ord { /// Original author in Rust: Thomas Backman <serenity@exscape.org> fn next_permutation(&mut self) -> bool { // These cases only have 1 permutation each, so we can't do anything. if self.len() < 2 { return false; } // Step 1: Identify the longest, rightmost weakly decreasing part of the vector let mut i = self.len() - 1; while i > 0 && self[i-1] >= self[i] { i -= 1; } // If that is the entire vector, this is the last-ordered permutation. if i == 0 { return false; } // Step 2: Find the rightmost element larger than the pivot (i-1) let mut j = self.len() - 1; while j >= i && self[j] <= self[i-1] { j -= 1; } // Step 3: Swap that element with the pivot self.swap(j, i-1); // Step 4: Reverse the (previously) weakly decreasing part self[i..].reverse(); true } fn prev_permutation(&mut self) -> bool { // These cases only have 1 permutation each, so we can't do anything. if self.len() < 2 { return false; } // Step 1: Identify the longest, rightmost weakly increasing part of the vector let mut i = self.len() - 1; while i > 0 && self[i-1] <= self[i] { i -= 1; } // If that is the entire vector, this is the first-ordered permutation. if i == 0 { return false; } // Step 2: Reverse the weakly increasing part self[i..].reverse(); // Step 3: Find the rightmost element equal to or bigger than the pivot (i-1) let mut j = self.len() - 1; while j >= i && self[j-1] < self[i-1] { j -= 1; } // Step 4: Swap that element with the pivot self.swap(i-1, j); true } } #[test] fn lexical() { let mut data = [1, 2, 3]; data.next_permutation(); assert_eq!(&data, &[1, 3, 2]); data.next_permutation(); assert_eq!(&data, &[2, 1, 3]); data.prev_permutation(); assert_eq!(&data, &[1, 3, 2]); data.prev_permutation(); assert_eq!(&data, &[1, 2, 3]); assert!(!data.prev_permutation()); let mut c = 0; while data.next_permutation() { c += 1; } assert_eq!(c, 5); }