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
}

• prehistoricpenguin: Thank you so much. I like both the code here and the one you left in the playground. I have asked the question in Reddit too, there is a promising answer: reddit.com/r/rust/comments/mldrsx/…, I think we may tack a look, maybe we can absorb the idea.
• prehistoricpenguin: All your comments are shining, I learned so much here.
• prehistoricpenguin: The algorithm with your fix is cleaner than the one in my post, however, I have a check that LLVM's c++ standard library's code: github.com/llvm-mirror/libcxx/blob/master/include/…, it's using the unclear version, I think it can be improved somehow.
• trent: Hmm, I forgot about rposition. That plus windows (although array_windows would still be nicer) does make the iterator version a lot cleaner by replacing the enumerate + filter_map + next_back dance
• trent: You can also use binary search on the monotonically-descending subslice to find the swap-with position