Is (was) the next-step-in-last-iteration a pattern in rust?

I was reading some old thread here and found the following code (and its variations) presented as 'more idiomatic':

The algorithm implemented generates the next permutation in three steps (simplified):

  1. find the longest decreasing tail
  2. find the smallest element in that tail greater than the element just before the tail
  3. complete the output

What I don't like about this code is that the further steps are embedded within the loop bodies of preceding steps. It gives me a feeling of "I cannot return a value from a loop, so I have to resort to nesting".

I would prefer this approach (also personally I would put those method chains on a single line, but rustfmt disagrees):

fn my_next_perm<T: PartialOrd + Copy>(permutation: &[T]) -> Option<Vec<T>> {
    let Some((i, &[val, ..])) = permutation
        .windows(2)
        .enumerate()
        .rev()
        .find(|(_, e)| e[0] < e[1])
    else {
        return None;
    };
    let (j, _) = permutation
        .iter()
        .enumerate()
        .rev()
        .find(|&(_, &e)| e > val)
        .expect("should stop at i+1 at most");
    let mut result = permutation.to_vec();
    result.swap(i, j);
    result[(i + 1)..].reverse();
    Some(result)
}

So is the former code really a good pattern in rust? Or am I using a feature that was not available back then?

1 Like

let-else statements were stabilised in 1.65.0 which was released in November 2022, so definitely a feature that was not around in 2019 when the answer you've linked was written

No if let, no slice patterns. But this would have worked.

    let (i, val) = match permutation
        .windows(2)
        .enumerate()
        .rev()
        .find(|(_, e)| e[0] < e[1])
    {
        Some((i, slice)) if slice.len() > 0 => (i, slice[0]),
        _ => return None,
    };

(Guess you don't really need the length check, I just mechanically transformed the pattern matching.)

3 Likes

Ok, but the manual match still looks reasonable to me. So the nesting was more of the author's preference than general recommendation?

Probably personal preference, the main thing that jumps out at me as "more idiomatic" within that thread is preferring iteration to manual indexing.

So more idiomatic, I don't know, but between yours and the one you linked to, I prefer yours. Slice patterns help.

Both should have comments to explain the operation. Which touches on a tangential point: when you're implementing a specific algorithm (as can often happen in combinatorics), sometimes being idiomatic goes out the window to accommodate the algorithm. [1]


  1. Tangent to the tangent: Visitor patterns are often nicer for these enumeration problems, in contrast with the iterators others may expect. ↩ī¸Ž

2 Likes

I like your version better, but as has been said in this thread some of the features weren't around in 2019.

Also my code was a straightforward rework of the OP's for loop version to use iterators + a few other small changes. It wasn't meant to be a perfectly idiomatic version of the code even then. Hence "more idiomatic" not simply "idiomatic".

3 Likes

It's possible to loosen the Copy bound to Clone like so.

fn my_next_perm<T: PartialOrd + Clone>(permutation: &[T]) -> Option<Vec<T>> {
    let Some((i, [val, ..])) = permutation
        .windows(2)
        .enumerate()
        .rev()
        .find(|(_, e)| e[0] < e[1])
    else {
        return None;
    };
    let (j, _) = permutation
        .iter()
        .enumerate()
        .rev()
        .find(|&(_, e)| e > val)
        .expect("should stop at i+1 at most");
    let mut result = permutation.to_vec();
    result.swap(i, j);
    result[(i + 1)..].reverse();
    Some(result)
}

And if you accept a &mut [T] instead of a &[T] you could do the swap and reverse directly on the slice, removing the need for a clone as well

3 Likes

Thanks for clarification.

Yes, I agree. I myself was considering making the &mut version, but I decided to keep the interface, so that it's an alternative implementation rather than implementation of something else.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.