I evaluated the Steinhaus-Johnston-Trotter algorithm (with Shimon Even's improvement), Heap's algorithm, and the Alternate Ive's algorithm and found this one (Heap's) to be the simplest to implement and the fastest (same conclusion as Robert Sedgewick in 1977).
Note that the iterator only returns a boolean. I figured it would make the most sense not to return the slice over again, to lessen any confusion about this being an in-place iterator versus a version that duplicates every permutation (which would be an easy thing to layer on top of this, if someone wanted).
Kelimion
commented
3 weeks ago
I evaluated the Steinhaus-Johnston-Trotter algorithm (with Shimon Even's improvement), Heap's algorithm, and the Alternate Ive's algorithm and found this one (Heap's) to be the simplest to implement and the fastest (same conclusion as Robert Sedgewick in 1977).
Note that the iterator only returns a boolean. I figured it would make the most sense not to return the slice over again, to lessen any confusion about this being an in-place iterator versus a version that duplicates every permutation (which would be an easy thing to layer on top of this, if someone wanted).