Permutohedron

https://docs.rs/permutohedron
Admin
Permutohedron is a Rust library for generating permutations of sequences using Heap's algorithm or...
Tokens:47,167
Snippets:432
Trust Score:9.1
Update:1 week ago
Show doc for...
Tokens:
Raw
### 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<T, F, C>(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<T, F, C>(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_<T, F, C>(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<Self> where Self: Sized

### Parameters
- **n** (usize) - Required - The number of elements to take.

### Return Value
Returns a `Take<Self>` iterator adapter.
```

--------------------------------

### fn partition<B, F>(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<B, F>(self, f: F) -> (B, B)

### Description
Consumes an iterator, creating two collections from it.

### Signature
```rust
fn partition<B, F>(self, f: F) -> (B, B)
where
    Self: Sized,
    B: Default + Extend<Self::Item>,
    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<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>

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<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>

### 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<F, R, const N: usize>(self, f: F) -> MapWindows<Self, F, N>
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<Self, F, N>` 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<T> 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<Self>

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<Self>

### 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<Self>
where
    Self: Sized,
```

### Parameters
- **n** (usize) - The number of elements to take.

### Return Value
Returns a `Take<Self>` 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<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);
}

```

--------------------------------

### 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<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);
}
```

--------------------------------

### 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<P>(self) -> P`

### Return Type
`P`

### Notes
- Available since 1.11.0 (const: unstable).
```

--------------------------------

### fn product<P>(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<P>(self) -> P

### Description
Iterates over the entire iterator, multiplying all the elements.

### Method
fn product

### Signature
```rust
fn product<P>(self) -> P
where
    Self: Sized,
    P: Product<Self::Item>,
```

### Return Value
- The product of all elements.

### Notes
- Version: 1.11.0 (const: unstable)
```

--------------------------------

### fn fold<B, F>(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<B, F>(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<B, F>(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<T>(xs: &mut [T]) -> Heap<T>` - Creates a new iterator for generating permutations.
- `next<T>(&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<Self>

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<Self>

### Description
Creates an iterator that skips the first `n` elements.

### Signature
```rust
fn skip(self, n: usize) -> Skip<Self>
where
    Self: Sized,
```

### Parameters
- **n** (usize) - The number of elements to skip.

### Return Value
Returns a `Skip<Self>` 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<F>(self, f: F) -> Inspect<Self, F> 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<Self, F>` 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<Ordering>. 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<I, F>(self, other: I, partial_cmp: F) -> Option<Ordering>
where
    Self: Sized,
    I: IntoIterator,
    F: FnMut(Self::Item, <I as IntoIterator>::Item) -> Option<Ordering>,
```

### 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<Ordering>`.

### Return Value
- **Option<Ordering>** - 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<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>

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<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>

### Description
An iterator adapter which, like `fold`, holds internal state, but unlike `fold`, produces a new iterator.

### Signature
```rust
fn scan<St, B, F>(self, initial_state: St, f: F) -> Scan<Self, St, F>
where
    Self: Sized,
    F: FnMut(&mut St, Self::Item) -> Option<B>,
```

### 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<Self, St, F>` 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<B>`, and `Result<(), E>`.

```APIDOC
## ControlFlow::continuing()

### Description
Creates a value representing continuation. Implemented for `()`, `Control<B>`, and `Result<(), E>`.

### Method
`ControlFlow::continuing() -> Self`

### Parameters
None.

### Returns
- `Self` - A value representing continuation.

### Implementations
- For `()`: returns `()`.
- For `Control<B>`: returns `Control::Continue`.
- For `Result<(), E>`: returns `Ok(())`.

### Example
```rust
let cont = Control::<i32>::continuing();
```
```

--------------------------------

### fn inspect<F>(self, f: F) -> Inspect<Self, F>

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<F>(self, f: F) -> Inspect<Self, F>

### Description
Does something with each element of an iterator, passing the value on.

### Signature
```rust
fn inspect<F>(self, f: F) -> Inspect<Self, F>
where
    Self: Sized,
    F: FnMut(&Self::Item),
```

### Parameters
- **f** (F) - A closure that takes a reference to each item.

### Return Value
Returns an `Inspect<Self, F>` iterator adapter.

### Notes
- Available since Rust 1.0.0.
- Const evaluation is unstable.
```

--------------------------------

### fn any<F>(&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<F>(&mut self, f: F) -> bool

### Description
Tests if any element of the iterator matches a predicate.

### Method
fn any

### Signature
```rust
fn any<F>(&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<Self::Item>

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<Self::Item>

### Description
Returns the minimum element of an iterator.

### Method
fn min

### Signature
```rust
fn min(self) -> Option<Self::Item>
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<F>(self, f: F) -> Option<Self::Item>

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<F>(self, f: F) -> Option<Self::Item>

### Description
Reduces the elements to a single one, by repeatedly applying a reducing operation.

### Signature
```rust
fn reduce<F>(self, f: F) -> Option<Self::Item>
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.
```
Tokens:
Raw