saturating_sub should fix it:
for i in (1..permutation.len().saturating_sub(1)).rev()
With len <= 1, the loop won't run.
2 Likes
Yep that did it.
"saturating_sub", I like it.
Of course I can use that in my original version, which allows removal of the outer length test and end up with:
fn next_permutation <T: PartialOrd + Copy> (permutation: &Vec<T>) -> Option<Vec<T>> {
for i in (0..permutation.len().saturating_sub(1)).rev() {
if permutation[i] < permutation[i + 1] {
for j in (0..permutation.len()).rev() {
if permutation[j] > permutation[i] {
let mut result: Vec<T> = permutation.clone();
result.swap(i, j);
result[(i + 1)..].reverse();
return Some(result)
}
}
}
}
None
}
Which is short and sweet and basically the same as Krishna's. Except without introducing the "next", "current", "val" temporaries. Normally I like to name things like that but as they are only used so little here I feel they add more confusion than they remove. Using i and j indexed values stays inline with the textual description of the algorithm.
But that is now down to a very minor difference in taste rather than "idiomatic" Rust I think.
My original point was to show that ++ and -- are not required if one has slices, ranges, iterators, etc available. The later resulting in more legible code. I doubt there are any performance benefits either. They are just C baggage that the descendants of C forgot to jettison 
The neat thing is that all the versions I have tried, from a very C like style to this, run in almost exactly the same time.
Thanks all, great hints for a noobie here.
1 Like
4 Likes
hellow,
Not passing references is something to think about. I'm not sure I understand what you are getting at in this case.though.
If I understand correctly I have three options:
- The parameter is not a reference, e.g. "(thing: Vec)"
In which case the caller is saying "here, have this, you own it, do what you like with it" and cannot ever use it again.
- The parameter is a reference, e.g. "(thing: &Vec)"
In which case the caller is only saying "here, look at this but don't touch" whilst retaining ownership and can use it again.
- The parameter is a mutable reference, e.g. "thing: &mut Vec"
In which case the caller is saying, "here, borrow this, do what you like with it, but I want it back" and can use it again.
Now, in this case I would of course like the function to take a look at the parameter but I may well want to use that thing again. I might want to show it to someone else. If I don't pass a reference I cannot do that. Like so:
let perm: Vec<u8> = b"ketormaa".to_vec();
let next = next_permutation(perm).unwrap();
println!("perm: {:?}, next: {:?}", perm, next);
FAIL: perm is borrowed after move.
Semantically next_permutaion has no need to own the input, what's he going to do with it apart from delete it? And it's inconvenient for the caller to give it away. So I think a reference is the correct thing here.
Or, did I get hold the wrong end of the stick yet again?
How using references or not impacts performance I have yet to investigate.
Of course there is another end of the stick:
I can define next_permutation to take a slice instead of a Vec:
fn next_permutation_slice <T: PartialOrd + Copy> (permutation: &[T]) -> Option<Vec<T>> {
Which is marginally prettier perhaps.And has the benefit that I can now call it with a slice or a Vec like so:
let perm1: &[u8] = b"ketormaa";
let next1 = next_permutation(&perm1).unwrap();
println!("perm1: {:?}, next1: {:?}", perm1, next1);
let perm2: Vec<u8> = b"ketormaa".to_vec();
let next2 = next_permutation(&perm2).unwrap();
println!("perm2: {:?}, next2: {:?}", perm2, next2);
To newbie to know what is best. I see no difference in performance between using Vect or slice so far.
1 Like
Taking a slice is a good habit to have, have you tried to call your function with an array? ([1, 4, 3, 2] for example)
I will go even further, if you ever make a library, you should take something like impl AsRef<[T]>, this will accept an even larger number of types.
Of course in this case it's fine to simply use a slice.
Also if you don't know it yet there is a tool that makes suggestions to improve code called Clippy, you can even run it on the playground.
1 Like
A &Vec<T> has no value over &[T] so you should always use slices instead of vec in this case. It makes code more flexible at no additional cost.
1 Like
The exact value a &Vec<T> provides is access to the following &self methods:
pub fn capacity(&self) -> usize;
pub fn as_slice(&self) -> &[T]; // which just gets the &[T] back, so doesn't add anything
pub fn as_ptr(&self) -> *const T; // which is defined on &[T] as well
So yeah. Unless you need to know the capacity of a Vec, &Vec is a rather useless type.
4 Likes
But knowing the capacity is useless because there isn't anything useful you can do with that information, as you can't modify the Vec. The main use for capacity is to reserve enough space to prevent frequent allocations in some performance critical section of code. I guess you could also use capacity for diagnostics, but that isn't the normal case.
Minor nit, as_ptr comes from slice.
1 Like
OK, slices it is. Works a treat, looks a bit neater. Arrays, [1, 4, 3, 2] work fine. Any thoughts of "AsRef" can wait for now.
I forgot about clippy...Oh boy, that next_permutation is part of 2000 lines of C++ I converted to Rust last weekend. Which in turn was a translation from C#. It works just fine but clippy has 230 suggestions for my attention now!
Thanks all.
3 Likes
Arrays work fine when you take a slice but not a Vec.
dies a little more inside
the only ever acceptable answer to those language lawyering questions is "you're sent on unpaid leave, no one wants to be stuck troubleshooting '"nifty' code like that" 
honestly it took some getting used to me for me too but overall, I'm happy rust doesn't have inline x++ and ++x (and that x+=1 simply returns () ) so never need to worry about evaluation order, or even undefined behavior madness when there's multiple of those in one statement, a little bit of typing convenience can't be worth that
5 Likes
So I just discovered the windows interator. Now my next_permutation() looks like this:
// Generate the next permutation lexicographically after a given permutation (if there is one).
fn next_permutation<T: PartialOrd + Copy>(permutation: &[T]) -> Option<Vec<T>> {
let mut result: Vec<T> = permutation.to_vec();
// Find the highest index i such that s[i] < s[i+1]. If no such index exists, the permutation is the last permutation
for w in result.windows(2).enumerate().rev() {
let i = w.0;
if result[i] < result[i + 1] {
// Find the highest index j > i such that s[j] > s[i]. Such a j must exist, since i+1 is such an index.
for j in (0..permutation.len()).rev() {
if permutation[j] > permutation[i] {
// Swap s[i] with s[j].
result.swap(i, j);
// Reverse the order of all of the elements after index i till the last element.
result[(i + 1)..].reverse();
return Some(result);
}
}
}
}
None
}
Which get's rid of that wonky looking saturated_sub of the previous version and is more true to the spirit of the algorithm description.
I like Rust more everyday
1 Like
Heh, now you are almost at my idiomatic version!
I have a great tutor !
Thanks.
4 Likes
When C was invented, I guess fluent-style chaining function calls were not yet invented... 
It would actually read better if the not syntax is designed to go before the method call but AFTER the dot:
let x = [1,2,3,4,5,6,7]
.iter()
.!any(|x| x < 5);
Yikes. Here is a great example of why I think "!" needs to die in all programming languages as a negation operator. It is almost completely invisible there.
Pascal-style (not, and, or) is so much better IMHO than !, &&, || for readability. I truly would like to work on a variant of the Rust language with the same semantics, but, and emphasis on eliminating nearly invisible C-isms etc. I like C, but, I also like Pascal. I've worked with so many languages over the years and I've come to the conclusions as follows:
- readability is nearly the most important thing when it comes long-term maintenance of big projects (especially maintaining someone else's code) - which "patterns", "styles", "methodologies" is much less important for maintainability than writing things with clear names and consistent formatting (or the ability to easily apply consistent formatting after the fact)
- Saving a few characters of typing is not useful if it compromises readability
- Long, meaningful names for things is almost always better than short
- terse is more often bad than good
- explicit is better than implicit for maintainability except where the implicitness is 100% obvious and unambiguous without much thought
4 Likes