mozilla/rust — pull request #13761 by exscape (2014-04-25 20:08:33+00:00)
Title: Add next_permutation and prev_permutation onto MutableTotalOrdVector<T>.

Okay, so first out, I'm no sure if this is okay as a pull request (without prior discussion or an RFC). However, considering that

> Pull requests will be treated as "review requests"

and the fact that the community is supposed to be friendly to strangers and beginners, I figured not too much could go wrong; worst case, the pull request is not accepted, right? :-)
I looked at the existing RFCs, but all of them felt bigger in scope than simply adding a few function (causing no backwards incompatibility).

Anyway. This adds two methods to mutable vectors (`MutableTotalOrdVector`): next_permutation() and prev_permutation().
They mutate the vector to the next/previous lexicographic permutation, *in place*.
The existing permutation functionality, [ImmutableCloneableVector::permutations()](http://static.rust-lang.org/doc/master/std/slice/trait.ImmutableCloneableVector.html#tymethod.permutations), uses iterators and clones the entire vector *each iteration*, resulting in bad performance. For even a 10-element vector, that causes 10! = 3628800 calls to clone(), on the entire 10-element vector.
It also uses a swapping algorithm which does not generate lexicographic permutations; if you want lexicographical permutations, as far as I can tell, Rust currently cannot provide that.

So does Rust need this? I don't know. I wanted to use it, and realized it didn't exist, so I created it. Others may disagree about the necessity, of course.

Sample benchmarks:

test bench_iterated_permutations_one_iter ... bench: 721 ns/iter (+/- 212)
test bench_lexicographic_permutations_one_iter ... bench: 14 ns/iter (+/- 1)
test bench_iterated_permutations_bulk ... bench: 2449743 ns/iter (+/- 328460)
test bench_lexicographic_permutations_bulk ... bench: 69704 ns/iter (+/- 2235)

51x faster per single iteration (one permutation per benchmark iteration), 35x faster to loop through all 5040 permutations of range(0,7) per benchmark iteration.

One possible (style-ish) issue with this code is the return types: they return `true` if successful, and `false` if the vector was already at the first/last permutation. This makes looping rather easy, but I'm not sure if it's considered "pretty", so to speak. However, since iterators are much too expensive, at least if returning a cloned vector each iteration is the only way to make them work, I found no better way to solve this, and at least IMHO it looks fine.
Also, I'm not sure if the comments inside the actual functions is considered excessive or not, but that is of course easily changed, if that would be the case.

BTW, I have ran more tests than actually submitted; the full suite would be excessive to submit, but can be viewed [here](https://github.com/exscape/Rust/blob/c70a5869fbe255a817abeaee4d19407c31ae1974/permutation-tests.rs) (please excuse the messy code).