# ETOOBUSY ðŸš€ minimal blogging for the impatient

# Permutations with Heap's Algorithm

**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!

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