TL;DR

All permutations over $N$ objects can be generated by Heap’s Algorithm.

It also seems that it’s pretty good at minimizing the number of movements of stuff around.

The good thing with the current version of the Wikipedia page (as of this writing) is the pseudo-code for an iterative (i.e. non-recursive) version of the algorithm. The following is taken from there, without the comments and with variable names that are a bit more readable in my opinion:

procedure generate(n : integer, A : array of any):
stack : array of integer
sp    : integer

for sp := 0; sp < n; sp += 1 do
stack[sp] := 0
end for

output(A)

sp := 0;
while sp < n do
if stack[sp] < sp then
if sp is even then
swap(A, A[sp])
else
swap(A[c[sp]], A[sp])
end if
output(A)
stack[sp] += 1
sp := 0
else
stack[sp] := 0
sp += 1
end if
end while


I’m particularly fond of iterative implementations, which probably makes me a bad functional programmer.

But there’s a reason for my bias, which I already talked about (I think): turning an iterative implementation into an iterator-based implementation is easier (at least for me!) and iterator-based implementations on stuff that can grow factorially can be a very, very interesting characteristic.

Here’s a corresponding Perl implementation, where we avoid taking parameter n explicitly and the input array is passed via @_:

sub permutations {
my @indexes = 0 .. $#_; my @stack = (0) x @indexes; output(@_[@indexes]); my$sp = 0;
while ($sp < @indexes) { if ($stack[$sp] <$sp) {
my $other =$sp % 2 ? $stack[$sp] : 0;
@indexes[$sp,$other] = @indexes[$other,$sp];
output(@_[@indexes]);
$stack[$sp]++;
$sp = 0; } else {$stack[\$sp++] = 0;
}
}
}


As a matter of fact, we use array @indexes to take the role of the input array A in the pseudocode, so that we avoid messing up directly with the array.

I really like how compact this implementation is!

Comments? Octodon, , GitHub, Reddit, or drop me a line!