next_permutation.rs

/// Permutes the `slice` into the next permutation, where the set of all
/// permutations is ordered lexicographically.
/// Returns `true` if there is a next permutation.
///
/// # Example
/// ```rust
/// let mut values: Vec<usize> = (0..3).collect();
/// while next_permutation(&mut values) {
///     println!("current permutation: {:?}", values);
/// }
/// ```
fn next_permutation<T: Ord>(slice: &mut [T]) -> bool {
    let last = slice.len().saturating_sub(1);
    if last == 0 {
        return false;
    }

    let mut i = last;
    loop {
        let i1 = i;
        i -= 1;

        if slice[i] < slice[i1] {
            let mut i2 = last;
            while slice[i] >= slice[i2] {
                i2 -= 1;
            }
            slice.swap(i, i2);
            slice[i1..].reverse();
            return true;
        }
        if i == 0 {
            slice.reverse();
            return false;
        }
    }
}