By satylogin, history, 5 days ago,

I was trying out problem https://codeforces.com/contest/1526/problem/D, and its implementation required us to have next_permutation. I couldn't find any reference for it in rust std lib, and since we can't import crates, I wrote a generic implementation that I could reuse across problems.

Just sharing this in case someone needs this:

/// Finds next lexographic permutation of given slice. If next larger permutation exists,
/// the slice would then have this and the return value would be true. If the slice
/// represents the largest lexicographic sequence, it updates the slice with smallest one
/// and returns false.
/// The type whose permutation is required must implement [Ord](std::cmp::Ord) trait.
pub fn next_permutation<T>(arr: &mut [T]) -> bool
where
T: std::cmp::Ord,
{
use std::cmp::Ordering;

// find 1st pair (x, y) from back which satisfies x < y
let last_ascending = match arr.windows(2).rposition(|w| w[0] < w[1]) {
Some(i) => i,
None => {
arr.reverse();
return false;
}
};

// In the remaining later segment, find the one which is just
// larger that the index found above.
// SAFETY: unwrap_err whill not panic since binary search will
// will never succeed since we never return equal ordering
let swap_with = arr[last_ascending + 1..]
.binary_search_by(|n| match arr[last_ascending].cmp(n) {
Ordering::Equal => Ordering::Less,
ord => ord,
})
.unwrap_err();
arr.swap(last_ascending, last_ascending + swap_with);
arr[last_ascending + 1..].reverse();
true
}