Rust implementation of next-permutation

Question

I am translating this next permutation algorithm in C++:

template<class BidirIt>
bool next_permutation(BidirIt first, BidirIt last)
{
    if (first == last) return false;
    BidirIt i = last;
    if (first == --i) return false;
  
    while (true) {
        BidirIt i1, i2;
  
        i1 = i;
        if (*--i < *i1) {
            i2 = last;
            while (!(*i < *--i2))
                ;
            std::iter_swap(i, i2);
            std::reverse(i1, last);
            return true;
        }
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Into this Rust code:

struct Solution;
impl Solution {
    pub fn next_permutation(nums: &mut Vec<i32>) -> bool{
        if nums.len() < 2 {
            return false;
        }
        let first = 0;
        let last = nums.len();
        let mut i = last - 1;
        loop {
            let i1 = i;
            i -= 1;

            if nums[i] < nums[i1] {
                let mut i2 = last;

                loop {
                    i2 -= 1;
                    if nums[i] < nums[i2] {
                        break;
                    }
                }
                let tmp = nums[i];
                nums[i] = nums[i2];
                nums[i2] = tmp;
                nums[i1..last].reverse();
                return true;
            }
            if i == first {
                nums[first..last].reverse();
                return false;
            }
        }
    }
}

Though it works, I think it's not very good-looking. I am a beginner in Rust; any improvement will be welcome!

Answer 1

In no particular order:

• Create test cases so you can have some confidence while refactoring.

• Don't create empty structs (Solution) just to give them functions. next_permutation is perfectly fine as a free function. If you have to create a bad API to satisfy LeetCode or whatever, write the good API first, and then wrap it. If the API required is so bad you can't wrap a good API with it, it's probably a waste of time.

• Use rustfmt.

• Accept &mut [T] instead of &mut Vec<T> when you don't need to change the size.

• let first = 0;
  let last = nums.len();
  

  Don't give unnecessary symbolic names to things that aren't used symbolically. 0 is far more obviously the index of the first element in a slice than first. Furthermore, you don't even need to provide the bounds of the slice when indexing with [..]; they're implied. So you need these even less than you perhaps thought.

• i, i1, i2 are meaningless. How about some descriptive names?

• I prefer to put each loop in a block with its state variables to limit the scope of the mutability.

• let i1 = i;
  

  Similar to the note on first and last above, don't make variables that can be trivially calculated from other variables. The relationship between i and i + 1 is way more obvious than i and i1.

• if nums[i] < nums[i + 1] { ... }
  

  Why is this body nested in the outer loop? The algorithm breaks fairly easily into four steps:

  1. Get the index of the rightmost ascending pair of values
  2. Get the index of the rightmost value greater than the first element of that pair
  3. Swap the values at these two indices
  4. Reverse the slice starting just after the first index.

  You have 2, 3, and 4 nested inside 1, which makes the algorithm look more complicated than it actually is.

• let tmp = nums[i];
  nums[i] = nums[i2];
  nums[i2] = tmp;
  

  Use nums.swap(i, i2) instead.

• As mentioned in the reddit comments, there's an iterator method rposition that finds the last item matching some predicate (if the iterator is one that can be iterated from both ends). You can use this to linearize the first (outer) loop, which may be easier to reason about. Don't go overboard, though: iterators are great for certain tasks and not so great for others. If you feel like the logic and flow of the code is better with a loop, just write the loop.

• As for the inner loop, since the trailing subslice is by definition monotonically decreasing, you can search for the swap point using binary search. It's not likely to make a big performance difference, though, and the logic might be a little harder to follow, so you might want to use rposition here as well.

Applied

pub fn next_permutation(nums: &mut [i32]) -> bool {
    use std::cmp::Ordering;
    // or use feature(array_windows) on nightly
    let last_ascending = match nums.windows(2).rposition(|w| w[0] < w[1]) {
        Some(i) => i,
        None => {
            nums.reverse();
            return false;
        }
    };

    let swap_with = nums[last_ascending + 1..]
        .binary_search_by(|n| i32::cmp(&nums[last_ascending], n).then(Ordering::Less))
        .unwrap_err(); // cannot fail because the binary search will never succeed
    nums.swap(last_ascending, last_ascending + swap_with);
    nums[last_ascending + 1..].reverse();
    true
}