Permutations with Heap's Algorithm


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


    sp := 0;
    while sp < n do
        if stack[sp] < sp then
            if sp is even then
                swap(A[0], A[sp])
                swap(A[c[sp]], A[sp])
            end if
            stack[sp] += 1
            sp := 0
            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;
   my $sp = 0;
   while ($sp < @indexes) {
      if ($stack[$sp] < $sp) {
         my $other = $sp % 2 ? $stack[$sp] : 0;
         @indexes[$sp, $other] = @indexes[$other, $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!