### Example: Generate All Permutations Using next_permutation Source: https://docs.rs/permutohedron/latest/permutohedron/trait.LexicalPermutation.html Shows how to use the LexicalPermutation trait to generate all permutations of a slice in lexical order. The loop calls next_permutation until it returns false, and the example asserts the resulting permutations and that the data is mutated in-place. ```rust 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]); ``` -------------------------------- ### Usage example for heap_recursive Source: https://docs.rs/permutohedron/latest/permutohedron/fn.heap_recursive.html?search=std%3A%3Avec Example that uses `heap_recursive` to generate all permutations of a slice of six integers, collecting each permutation into a vector. The example asserts that the number of permutations is 720, which is 6!. ```rust use permutohedron::heap_recursive; let mut data = [1, 2, 3, 4, 5, 6]; let mut permutations = Vec::new(); heap_recursive(&mut data, |permutation| { permutations.push(permutation.to_vec()) }); assert_eq!(permutations.len(), 720); ``` -------------------------------- ### Heap struct implementation with new, get, and get_mut methods Source: https://docs.rs/permutohedron/latest/src/permutohedron/lib.rs.html Implements methods for the Heap struct: new creates a Heap, panicking if the data length exceeds MAXHEAP; get returns an immutable reference to the inner data; get_mut returns a mutable reference. ```rust impl<'a, T, Data: ?Sized> Heap<'a, Data, T> where Data: AsMut<[T]> { /// Create a new `Heap`. /// /// ***Panics*** if the number of elements is too large (see `MAXHEAP`) /// /// The `heap_recursive` function has no length limit, but /// note that for *n* elements there are *n!* (*n* factorial) permutations, /// which gets impractical for surprisingingly small values of *n* anyway. pub fn new(data: &'a mut Data) -> Self { assert!(data.as_mut().len() <= MAXHEAP); Heap { data: data, c: [0; MAXHEAP - 1], n: !0, _element: PhantomData, } } /// Return a reference to the inner data pub fn get(&self) -> &Data { self.data } /// Return a mutable reference to the inner data pub fn get_mut(&mut self) -> &mut Data { self.data } } ``` -------------------------------- ### heap_recursive function with usage example Source: https://docs.rs/permutohedron/latest/src/permutohedron/lib.rs.html Defines the recursive Heap's algorithm function. The closure can return () or a Control value to break early. The doc example shows generating all 720 permutations of a 6-element array. ```rust /// Heap's algorithm for generating permutations, recursive version. /// /// The recursive algorithm supports slices of any size (even though /// only a small number of elements is practical), and is generally /// a bit faster than the iterative version. /// /// The closure `f` may return either `()` to simply run through all /// permutations, or a `Control` value that permits breaking the /// iteration early. /// /// ``` /// use permutohedron::heap_recursive; /// /// let mut data = [1, 2, 3, 4, 5, 6]; /// let mut permutations = Vec::new(); /// heap_recursive(&mut data, |permutation| { /// permutations.push(permutation.to_vec()) /// }); /// /// assert_eq!(permutations.len(), 720); /// ``` pub fn heap_recursive(xs: &mut [T], mut f: F) -> C where F: FnMut(&mut [T]) -> C, C: ControlFlow, { match xs.len() { 0 | 1 => f(xs), 2 => { // [1, 2], [2, 1] try_control!(f(xs)); xs.swap(0, 1); f(xs) } n => heap_unrolled_(n, xs, &mut f), } } ``` -------------------------------- ### permutohedron lib.rs source code Source: https://docs.rs/permutohedron/latest/src/permutohedron/lib.rs.html?search=std%3A%3Avec Full source code of the permutohedron crate's lib.rs, including feature flags, heap_recursive function, Heap struct, and documentation examples. ```rust #![cfg_attr(not(feature = "std"), no_std)] //! //! ## Crate Feature Flags //! //! - `std` //! + Default. Disabling `std` requires Rust 1.6 or later //! + Disabling `std` makes the crate a `#![no_std]` crate (works with core) #[cfg(not(feature = "std"))] extern crate core as std; use std::marker::PhantomData; pub use lexical::LexicalPermutation; mod lexical; #[macro_use] pub mod control; use control::ControlFlow; /// Heap's algorithm for generating permutations, recursive version. /// /// The recursive algorithm supports slices of any size (even though /// only a small number of elements is practical), and is generally /// a bit faster than the iterative version. /// /// The closure `f` may return either `()` to simply run through all /// permutations, or a `Control` value that permits breaking the /// iteration early. /// /// ``` /// use permutohedron::heap_recursive; /// /// let mut data = [1, 2, 3, 4, 5, 6]; /// let mut permutations = Vec::new(); /// heap_recursive(&mut data, |permutation| { /// permutations.push(permutation.to_vec()) /// }); /// /// assert_eq!(permutations.len(), 720); /// ``` pub fn heap_recursive(xs: &mut [T], mut f: F) -> C where F: FnMut(&mut [T]) -> C, C: ControlFlow, { match xs.len() { 0 | 1 => f(xs), 2 => { // [1, 2], [2, 1] try_control!(f(xs)); xs.swap(0, 1); f(xs) } n => heap_unrolled_(n, xs, &mut f), } } // TODO: Find a more parallel version with less data dependencies: // i.e. don't swap the same items (for example index 0) every time. /// Unrolled version of heap's algorithm due to Sedgewick fn heap_unrolled_(n: usize, xs: &mut [T], f: &mut F) -> C where F: FnMut(&mut [T]) -> C, C: ControlFlow, { debug_assert!(n >= 3); match n { 3 => { // [1, 2, 3], [2, 1, 3], [3, 1, 2], [1, 3, 2], [2, 3, 1], [3, 2, 1] try_control!(f(xs)); xs.swap(0, 1); try_control!(f(xs)); xs.swap(0, 2); try_control!(f(xs)); xs.swap(0, 1); try_control!(f(xs)); xs.swap(0, 2); try_control!(f(xs)); xs.swap(0, 1); f(xs) } n => { for i in 0..n - 1 { try_control!(heap_unrolled_(n - 1, xs, f)); let j = if n % 2 == 0 { i } else { 0 }; // One swap *between* each iteration. xs.swap(j, n - 1); } heap_unrolled_(n - 1, xs, f) } } } /// Maximum number of elements we can generate permutations for using /// Heap's algorithm (iterative version). pub const MAXHEAP: usize = 16; /// Heap's algorithm for generating permutations. /// /// An iterative method of generating all permutations of a sequence. /// /// Note that for *n* elements there are *n!* (*n* factorial) permutations. /// /// ``` /// use permutohedron::Heap; /// /// let mut data = vec![1, 2, 3]; /// let heap = Heap::new(&mut data); /// /// let mut permutations = Vec::new(); /// for data in heap { /// permutations.push(data.clone()); /// } /// /// assert_eq!(permutations.len(), 6); /// ``` // lock the repr since it performs the best in this order..(?) #[repr(C)] pub struct Heap<'a, Data: 'a + ?Sized, T: 'a> { data: &'a mut Data, // c, and n: u8 is enough range. // u32 performs better for n, u8 for c. // n: == !0 at start, 0 after first permutation is emitted n: u32, // c[x] is the counter for the (x + 1) th location c: [u8; MAXHEAP - 1], _element: PhantomData<&'a mut T> } impl<'a, T, Data: ?Sized> Heap<'a, Data, T> where Data: AsMut<[T]> { /// Create a new `Heap`. /// /// ***Panics*** if the number of elements is too large (see `MAXHEAP`) /// /// The `heap_recursive` function has no length limit, but /// note that for *n* elements there are *n!* (*n* factorial) permutations, /// which gets impractical for surprisingingly small values of *n* anyway. pub fn new(data: &'a mut Data) -> Self { assert!(data.as_mut().len() <= MAXHEAP); Heap { data: data, c: [0; MAXHEAP - 1], n: !0, _element: PhantomData, } } /// Return a reference to the inner data pub fn get(&self) -> &Data { self.data } /// Return a mutable reference to the inner data ``` -------------------------------- ### Using heap_recursive to collect permutations Source: https://docs.rs/permutohedron/latest/permutohedron/fn.heap_recursive.html?search=u32+-%3E+bool Example usage of heap_recursive that collects all permutations of a six-element slice into a vector. The closure pushes each permutation into the vector, and the example asserts that 720 permutations are generated. ```rust use permutohedron::heap_recursive; let mut data = [1, 2, 3, 4, 5, 6]; let mut permutations = Vec::new(); heap_recursive(&mut data, |permutation| { permutations.push(permutation.to_vec()) }); assert_eq!(permutations.len(), 720); ``` -------------------------------- ### MAXHEAP constant and Heap struct with usage example Source: https://docs.rs/permutohedron/latest/src/permutohedron/lib.rs.html Defines MAXHEAP as 16 and the iterative Heap struct. The doc example shows generating all 6 permutations of a 3-element vector. The struct panics if the number of elements exceeds MAXHEAP. ```rust /// Maximum number of elements we can generate permutations for using /// Heap's algorithm (iterative version). pub const MAXHEAP: usize = 16; /// Heap's algorithm for generating permutations. /// /// An iterative method of generating all permutations of a sequence. /// /// Note that for *n* elements there are *n!* (*n* factorial) permutations. /// /// ``` /// use permutohedron::Heap; /// /// let mut data = vec![1, 2, 3]; /// let heap = Heap::new(&mut data); /// /// let mut permutations = Vec::new(); /// for data in heap { /// permutations.push(data.clone()); /// } /// /// assert_eq!(permutations.len(), 6); /// ``` // lock the repr since it performs the best in this order..(?) #[repr(C)] pub struct Heap<'a, Data: 'a + ?Sized, T: 'a> { data: &'a mut Data, // c, and n: u8 is enough range. // u32 performs better for n, u8 for c. // n: == !0 at start, 0 after first permutation is emitted n: u32, // c[x] is the counter for the (x + 1) th location c: [u8; MAXHEAP - 1], _element: PhantomData<&'a mut T> } ``` -------------------------------- ### Generate permutations with Heap Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Creates a Heap from a mutable vector and iterates over all permutations, collecting them into a Vec. The example asserts that the number of permutations is 6 for 3 elements. ```rust use permutohedron::Heap; let mut data = vec![1, 2, 3]; let heap = Heap::new(&mut data); let mut permutations = Vec::new(); for data in heap { permutations.push(data.clone()); } assert_eq!(permutations.len(), 6); ``` -------------------------------- ### Heap struct definition and implementation Source: https://docs.rs/permutohedron/latest/src/permutohedron/lib.rs.html?search=u32+-%3E+bool Definition of the Heap struct and its implementation. The struct uses a repr(C) layout for performance. The new method panics if the number of elements exceeds MAXHEAP (16). Includes get method to return a reference to the inner data. ```rust // lock the repr since it performs the best in this order..(?) #[repr(C)] pub struct Heap<'a, Data: 'a + ?Sized, T: 'a> { data: &'a mut Data, // c, and n: u8 is enough range. // u32 performs better for n, u8 for c. // n: == !0 at start, 0 after first permutation is emitted n: u32, // c[x] is the counter for the (x + 1) th location c: [u8; MAXHEAP - 1], _element: PhantomData<&'a mut T> } impl<'a, T, Data: ?Sized> Heap<'a, Data, T> where Data: AsMut<[T]> { /// Create a new `Heap`. /// /// ***Panics*** if the number of elements is too large (see `MAXHEAP`) /// /// The `heap_recursive` function has no length limit, but /// note that for *n* elements there are *n!* (*n* factorial) permutations, /// which gets impractical for surprisingingly small values of *n* anyway. pub fn new(data: &'a mut Data) -> Self { assert!(data.as_mut().len() <= MAXHEAP); Heap { data: data, c: [0; MAXHEAP - 1], n: !0, _element: PhantomData, } } /// Return a reference to the inner data pub fn get(&self) -> &Data { self.data } /// Return a mutable reference to the inner data } ``` -------------------------------- ### Heap::new Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E Creates a new Heap instance for generating permutations of the given data. Panics if the number of elements is too large. ```APIDOC ## Heap::new ### Description Creates a new `Heap` for generating permutations of the given data. Panics if the number of elements is too large (see `MAXHEAP`). ### Method `pub fn new(data: &'a mut Data) -> Self` ### Parameters - **data** (`&'a mut Data`) - Required - The mutable reference to the data sequence to permute. ### Panics Panics if the number of elements is too large (see `MAXHEAP`). ### Example ```rust use permutohedron::Heap; let mut data = vec![1, 2, 3]; let heap = Heap::new(&mut data); ``` ``` -------------------------------- ### take Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=u32+-%3E+bool Creates an iterator that yields the first n elements, or fewer if the underlying iterator ends sooner. ```APIDOC ## take ### Description Creates an iterator that yields the first `n` elements, or fewer if the underlying iterator ends sooner. ### Method take ### Signature fn take(self, n: usize) -> Take where Self: Sized ### Parameters - **n** (usize) - Required - The number of elements to take. ### Return Value Returns a `Take` iterator adapter. ``` -------------------------------- ### fn partition(self, f: F) -> (B, B) Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Consumes an iterator, creating two collections from it. ```APIDOC ## fn partition(self, f: F) -> (B, B) ### Description Consumes an iterator, creating two collections from it. ### Signature ```rust fn partition(self, f: F) -> (B, B) where Self: Sized, B: Default + Extend, F: FnMut(&Self::Item) -> bool, ``` ### Parameters - **f** (F) - A closure that determines which collection each item goes into. ### Return Value Returns a tuple of two collections: one for items where `f` returns `true`, and one for items where `f` returns `false`. ### Notes - No version information provided. ``` -------------------------------- ### fn map_windows(self, f: F) -> MapWindows Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Calls the given function f for each contiguous window of size N over self and returns an iterator over the outputs of f. ```APIDOC ## fn map_windows(self, f: F) -> MapWindows ### Description Calls the given function `f` for each contiguous window of size `N` over `self` and returns an iterator over the outputs of `f`. Like `slice::windows()`, the windows during mapping overlap as well. ### Signature ```rust fn map_windows(self, f: F) -> MapWindows where Self: Sized, F: FnMut(&[Self::Item; N]) -> R, ``` ### Parameters - **f** (F) - A closure that takes a reference to an array of `N` items and returns a value. ### Return Value Returns a `MapWindows` iterator adapter. ### Notes - This is a nightly-only experimental API (`iter_map_windows`). - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### Heap::new Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Creates a new Heap instance from a mutable reference to the data. Panics if the number of elements is too large (see MAXHEAP). ```APIDOC ## Heap::new ### Description Creates a new `Heap` instance from a mutable reference to the data. Panics if the number of elements is too large (see `MAXHEAP`). ### Method `pub fn new(data: &'a mut Data) -> Self` ### Parameters - **data** (`&'a mut Data`) - Required - Mutable reference to the data sequence to permute. ### Panics Panics if the number of elements is too large (see `MAXHEAP`). ### Example ```rust use permutohedron::Heap; let mut data = vec![1, 2, 3]; let heap = Heap::new(&mut data); ``` ``` -------------------------------- ### Trait LexicalPermutation Source: https://docs.rs/permutohedron/latest/permutohedron/trait.LexicalPermutation.html?search=std%3A%3Avec Documentation for the LexicalPermutation trait, including its required methods and an example usage. ```APIDOC ## Trait LexicalPermutation ### Description Permute a slice into its next or previous permutation (in lexical order). This trait is dyn compatible. ### Required Methods #### fn next_permutation(&mut self) -> bool Return `true` if the slice was permuted, `false` if it is already at the last ordered permutation. #### fn prev_permutation(&mut self) -> bool Return `true` if the slice was permuted, `false` if it is already at the first ordered permutation. ### Implementations on Foreign Types #### impl LexicalPermutation for [T] where T: Ord - `fn next_permutation(&mut self) -> bool` - `fn prev_permutation(&mut self) -> bool` ### Example ```rust 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]); ``` ``` -------------------------------- ### control module Source: https://docs.rs/permutohedron/latest/permutohedron/index.html Control flow for callbacks. ```APIDOC ## control module ### Description Control flow for callbacks. ### Contents - Provides types and utilities for controlling the flow of callback-based permutation generation. ``` -------------------------------- ### Heap::reset Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Resets the permutations walker without changing the data, allowing generation of permutations again with the current state as starting point. ```APIDOC ## Heap::reset ### Description Resets the permutations walker without changing the data. It allows generating permutations again with the current state as starting point. ### Method `pub fn reset(&mut self)` ### Example ```rust use permutohedron::Heap; let mut data = vec![1, 2, 3]; let mut heap = Heap::new(&mut data); // iterate through permutations... heap.reset(); ``` ``` -------------------------------- ### fn take(self, n: usize) -> Take Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Creates an iterator that yields the first n elements, or fewer if the underlying iterator ends sooner. ```APIDOC ## fn take(self, n: usize) -> Take ### Description Creates an iterator that yields the first `n` elements, or fewer if the underlying iterator ends sooner. ### Signature ```rust fn take(self, n: usize) -> Take where Self: Sized, ``` ### Parameters - **n** (usize) - The number of elements to take. ### Return Value Returns a `Take` iterator adapter that yields at most `n` elements. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### Heap::get Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Returns a reference to the inner data. ```APIDOC ## Heap::get ### Description Returns a reference to the inner data. ### Method `pub fn get(&self) -> &Data` ### Returns - **&Data** - Immutable reference to the inner data. ### Example ```rust use permutohedron::Heap; let mut data = vec![1, 2, 3]; let heap = Heap::new(&mut data); let inner = heap.get(); ``` ``` -------------------------------- ### LexicalPermutation trait and implementation for slices Source: https://docs.rs/permutohedron/latest/src/permutohedron/lexical.rs.html Defines the LexicalPermutation trait with next_permutation and prev_permutation methods, and implements them for slices of Ord types. The implementation mutates the slice in-place and returns true if a permutation was found, false if at the boundary. The doc example shows generating all permutations of [1,2,3] and asserts the final state is [3,2,1]. ```rust /// 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 LexicalPermutation for [T] where T: Ord { /// Original author in Rust: Thomas Backman 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); } ``` -------------------------------- ### LexicalPermutation trait and implementation for slices Source: https://docs.rs/permutohedron/latest/src/permutohedron/lexical.rs.html?search=u32+-%3E+bool Defines the LexicalPermutation trait with next_permutation and prev_permutation methods, and implements it for slices of Ord types. The implementation mutates the slice in-place and returns true if a permutation was performed, false if the slice is already at the first or last ordered permutation. Includes a doc example showing how to generate all permutations of [1,2,3] and a test function verifying the behavior. ```rust /// 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 LexicalPermutation for [T] where T: Ord { /// Original author in Rust: Thomas Backman 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); } ``` -------------------------------- ### by_ref Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=u32+-%3E+bool Creates a “by reference” adapter for this instance of Iterator. ```APIDOC ## by_ref ### Description Creates a “by reference” adapter for this instance of `Iterator`. ### Method by_ref ### Signature fn by_ref(&mut self) -> &mut Self where Self: Sized ### Return Value Returns a mutable reference to the iterator. ``` -------------------------------- ### product Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Iterates over the entire iterator, multiplying all the elements. ```APIDOC ## product ### Description Iterates over the entire iterator, multiplying all the elements. ### Method `fn product

(self) -> P` ### Return Type `P` ### Notes - Available since 1.11.0 (const: unstable). ``` -------------------------------- ### fn product

(self) -> P Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E Iterates over the entire iterator, multiplying all the elements. ```APIDOC ## fn product

(self) -> P ### Description Iterates over the entire iterator, multiplying all the elements. ### Method fn product ### Signature ```rust fn product

(self) -> P where Self: Sized, P: Product, ``` ### Return Value - The product of all elements. ### Notes - Version: 1.11.0 (const: unstable) ``` -------------------------------- ### fn fold(self, init: B, f: F) -> B Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Folds every element into an accumulator by applying an operation, returning the final result. ```APIDOC ## fn fold(self, init: B, f: F) -> B ### Description Folds every element into an accumulator by applying an operation, returning the final result. ### Signature ```rust fn fold(self, init: B, f: F) -> B where Self: Sized, F: FnMut(B, Self::Item) -> B, ``` ### Parameters - **init** (B) - The initial accumulator value. - **f** (F) - A closure that takes the accumulator and the next item, returning the new accumulator. ### Return Value Returns the final accumulator value of type `B`. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### fn by_ref(&mut self) -> &mut Self Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Creates a “by reference” adapter for this instance of Iterator. ```APIDOC ## fn by_ref(&mut self) -> &mut Self ### Description Creates a “by reference” adapter for this instance of `Iterator`. ### Signature ```rust fn by_ref(&mut self) -> &mut Self where Self: Sized, ``` ### Return Value Returns a mutable reference to the iterator. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### Heap Source: https://docs.rs/permutohedron/latest/permutohedron/index.html Heap's algorithm for generating permutations (iterative version). ```APIDOC ## Heap ### Description Heap's algorithm for generating permutations (iterative version). ### Struct Methods - `new(xs: &mut [T]) -> Heap` - Creates a new iterator for generating permutations. - `next(&mut self) -> Option<&mut [T]>` - Returns the next permutation, or `None` when exhausted. ### Parameters - **xs** (&mut [T]) - Required - The slice to generate permutations of. ### Returns - **Option<&mut [T]>** - The next permutation, or `None` when exhausted. ``` -------------------------------- ### fn skip(self, n: usize) -> Skip Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Creates an iterator that skips the first n elements. ```APIDOC ## fn skip(self, n: usize) -> Skip ### Description Creates an iterator that skips the first `n` elements. ### Signature ```rust fn skip(self, n: usize) -> Skip where Self: Sized, ``` ### Parameters - **n** (usize) - The number of elements to skip. ### Return Value Returns a `Skip` iterator adapter that skips the first `n` elements. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### inspect Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=u32+-%3E+bool Does something with each element of an iterator, passing the value on. ```APIDOC ## inspect ### Description Does something with each element of an iterator, passing the value on. ### Method inspect ### Signature fn inspect(self, f: F) -> Inspect where Self: Sized, F: FnMut(&Self::Item) ### Parameters - **f** (F) - Required - A function that takes a reference to each item. ### Return Value Returns an `Inspect` iterator adapter. ``` -------------------------------- ### partial_cmp_by Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Lexicographically compares the elements of this Iterator with those of another using a specified comparison function that returns an Option. This is a nightly-only experimental API. ```APIDOC ## partial_cmp_by ### Description Lexicographically compares the elements of this `Iterator` with those of another with respect to the specified comparison function. ### Signature ```rust fn partial_cmp_by(self, other: I, partial_cmp: F) -> Option where Self: Sized, I: IntoIterator, F: FnMut(Self::Item, ::Item) -> Option, ``` ### Parameters - **other** (I) - The iterator to compare against. - **partial_cmp** (F) - A comparison function that takes an item from each iterator and returns an `Option`. ### Return Value - **Option** - The result of the lexicographic comparison, or `None` if the elements are not comparable. ### Notes - This is a nightly-only experimental API (`iter_order_by`). - Available since 1.5.0 (const: unstable). ``` -------------------------------- ### fn scan(self, initial_state: St, f: F) -> Scan Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html An iterator adapter which, like fold, holds internal state, but unlike fold, produces a new iterator. ```APIDOC ## fn scan(self, initial_state: St, f: F) -> Scan ### Description An iterator adapter which, like `fold`, holds internal state, but unlike `fold`, produces a new iterator. ### Signature ```rust fn scan(self, initial_state: St, f: F) -> Scan where Self: Sized, F: FnMut(&mut St, Self::Item) -> Option, ``` ### Parameters - **initial_state** (St) - The initial state for the scan. - **f** (F) - A closure that takes the current state and the next item, returning an optional output. ### Return Value Returns a `Scan` iterator adapter. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### control module Source: https://docs.rs/permutohedron/latest/permutohedron/index.html?search= Control flow for callbacks. This module provides utilities for controlling the flow of callback-based permutation generation. ```APIDOC ## control module ### Description Control flow for callbacks. This module provides utilities for controlling the flow of callback-based permutation generation. ### Usage Use the control module to manage early termination or other flow control in callback-based permutation functions. ### Example ```rust use permutohedron::control::Control; // Example usage with heap_recursive ``` ``` -------------------------------- ### ControlFlow::continuing() Source: https://docs.rs/permutohedron/latest/src/permutohedron/control.rs.html?search=u32+-%3E+bool Creates a value representing continuation. Implemented for `()`, `Control`, and `Result<(), E>`. ```APIDOC ## ControlFlow::continuing() ### Description Creates a value representing continuation. Implemented for `()`, `Control`, and `Result<(), E>`. ### Method `ControlFlow::continuing() -> Self` ### Parameters None. ### Returns - `Self` - A value representing continuation. ### Implementations - For `()`: returns `()`. - For `Control`: returns `Control::Continue`. - For `Result<(), E>`: returns `Ok(())`. ### Example ```rust let cont = Control::::continuing(); ``` ``` -------------------------------- ### fn inspect(self, f: F) -> Inspect Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Does something with each element of an iterator, passing the value on. ```APIDOC ## fn inspect(self, f: F) -> Inspect ### Description Does something with each element of an iterator, passing the value on. ### Signature ```rust fn inspect(self, f: F) -> Inspect where Self: Sized, F: FnMut(&Self::Item), ``` ### Parameters - **f** (F) - A closure that takes a reference to each item. ### Return Value Returns an `Inspect` iterator adapter. ### Notes - Available since Rust 1.0.0. - Const evaluation is unstable. ``` -------------------------------- ### fn any(&mut self, f: F) -> bool Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E Tests if any element of the iterator matches a predicate. ```APIDOC ## fn any(&mut self, f: F) -> bool ### Description Tests if any element of the iterator matches a predicate. ### Method fn any ### Signature ```rust fn any(&mut self, f: F) -> bool where Self: Sized, F: FnMut(Self::Item) -> bool, ``` ### Parameters - **f** (F) - Required - The predicate function. ### Return Value - `true` if any element matches the predicate, `false` otherwise. ### Notes - Version: 1.0.0 (const: unstable) ``` -------------------------------- ### fn min(self) -> Option Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html?search=Option%3CT%3E%2C+%28T+-%3E+U%29+-%3E+Option%3CU%3E Returns the minimum element of an iterator. ```APIDOC ## fn min(self) -> Option ### Description Returns the minimum element of an iterator. ### Method fn min ### Signature ```rust fn min(self) -> Option where Self: Sized, Self::Item: Ord, ``` ### Return Value - The minimum element, or `None` if the iterator is empty. ### Notes - Version: 1.0.0 (const: unstable) ``` -------------------------------- ### fn reduce(self, f: F) -> Option Source: https://docs.rs/permutohedron/latest/permutohedron/struct.Heap.html Reduces the elements to a single one, by repeatedly applying a reducing operation. ```APIDOC ## fn reduce(self, f: F) -> Option ### Description Reduces the elements to a single one, by repeatedly applying a reducing operation. ### Signature ```rust fn reduce(self, f: F) -> Option where Self: Sized, F: FnMut(Self::Item, Self::Item) -> Self::Item, ``` ### Parameters - **f** (F) - A closure that takes two items and returns a single item. ### Return Value Returns `Some` of the reduced value, or `None` if the iterator is empty. ### Notes - Available since Rust 1.51.0. - Const evaluation is unstable. ```