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[0], 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!