satylogin's blog

By satylogin, 3 years ago, In English

I was trying out problem https://codeforces.me/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::Greater, ord => ord, }) .unwrap_err(); arr.swap(last_ascending, last_ascending + swap_with); arr[last_ascending + 1..].reverse(); true }

I added this on github: https://github.com/satylogin/cp-lib

I will probably add couple more algo and ds there as and when needed.

Submission for above problem in case someone is interested: https://codeforces.me/contest/1526/submission/119132920

  • Vote: I like it
  • +18
  • Vote: I do not like it

| Write comment?