Lazy Heap's Permutation Algorithm

[jonnyso]

Hey there,

I've been trying to implement Heap's algorithm, however every example I found so far would create an array with every permutation. This is my attempt to create a "lazy" version of it, an iterator the figures out the next iteration as you call next() and doesn't create a potentially huge vec to store the permutations.

Rust Playground

There was a Bug at the end that would break permutations with a length greater than 4:

if depth > 2 {
    //if depth == value.len() {
    //    self.stack
    //        .extend((2..value.len()).rev().map(|index| (index, 0)));
    //} else {
    //    self.stack.push((depth - 1, 0));
    //}
    // Fixing a bug for it to generate stacks properly when len is
    // greater than 4
    self.stack
            .extend((2..depth).rev().map(|index| (index, 0)));
}

[quinedot]

You can avoid the lifetime; you just need T: Clone. (You probably could have avoided &&str if you had used &T where T: ?Sized too, but I didn't test this.)

You can avoid the Option with some use of std::mem::take.

Playground after these changes.

---

You could change Permut to hold a &mut [T] that gets permuted in place if you use a visitor pattern (or lending iterator pattern -- not a trait available in the standard library yet). Then you could avoid cloning altogether.

[jonnyso]

Thanks ! That's really helpful !