Revisiting Heap’s Algorithm in JavaScript

Back in March last year I presented an implementation of Heap’s Algorithm – an algorithm devised to generate all permutations of a set of items – in JavaScript. The article was interesting to write because in doing so I had found a bug in the pseudo-code on the Wikipedia page for the algorithm, which led to a discussion with the main editor for the page on how to make it better.

Fast forward to yesterday. That morning I listened to a presentation on programming in a functional style in C#. The presenter, Eric Lippert, mentioned he regularly visited the Code Review site on StackOverflow. I’d never heard of it, so I popped over there to take a look. And there, labeled JavaScript was a question about some code that did something with permutations. Time to revisit Heap, I thought.

Trouble was, as I looked at my code, I was disappointed with a couple of issues that now seemed obvious. These weren’t issues with its correct running (after all, it passed my tests), but issues with how I’d written it. It seemed overly complex (ifs all over the place, and two for loops?), it didn’t pass JSLint (the same issue I had here with recursion), and, to my horror, I saw that the function modified the input array. Since I am investigating functional programming in JavaScript at the moment, immutable data is at the forefront of my thinking. Last year? Eh, whatever, not so much. Hence I did a little bit of rewriting.

var generatePermutations = function (items, process) {
  "use strict";
  var 
    mutableItems = items.slice(),
    isEven = function (n) {
      return (n & 1) === 0;
    },
    permute = function (itemArray, x, last) {
      if (isEven(last)) { x = 0; }

      var temp = itemArray[x];
      itemArray[x] = itemArray[last];
      itemArray[last] = temp;
    },
    generate = function generateNext(last, process) {
      var i;
      if (last === 0) {
        process(mutableItems);
      }
      else {
        for (i = 0; i < last; i += 1) {
          generateNext(last - 1, process);
          permute(mutableItems, i, last);
        }
        generateNext(last - 1, process);
      }
    };

  generate(mutableItems.length - 1, process);
};

The first thing to note is the copying of the input array items into an internal array that I can mess with to my heart’s content. No one outside this function will notice any changes. Next is the encapsulation of the bit-twiddling that needed a comment in the previous version to explain what was going on into its own function, isEven(). Next, I changed the original swap function into a permute function that does a little more. In the algorithm the two for loops are there because of the different swaps. If the value of last is even the zeroth item is swapped with the last item, otherwise the ith item is swapped with the last one. With the permute function I hid all that away and so was able to get it down to one for loop. As, yes, I agree that this new function mutates the copy of the array of items but at least it is totally encapsulated inside the outer function. (I did have at one point change these internal functions return a copy of the changed array instead of changing it directly, but then decided that it was a little overkill for such a simple routine.)

Anyway, there you have it: the new implementation of Heap’s Algorithm. Until the next one.

  Loading links to posts on similar topics...

3 Responses

#1 Luca said...

15-Jan-16 3:31 PM

Hi, sorry but just a silly stupid remark this code does not work for an empty array ... the permutations of an empty array is an "empty set of arrays".

Here a modified version ;)

#2 julian m bucknall said...

15-Jan-16 3:54 PM

Nice one, @Luca! You are absolutely right, nice catch.

See? Code is never finished...

#3 imma said...

23-Feb-16 7:40 AM

Hi & thank you, I loved the article and was inspired to do a version with recursion instead of a loop

In case it's interesting to anyone :

function heap(items){
    return part([],items);

    function part(done,rest){
        return rest.length?
            part(done,tail(rest))
                .concat(part(done.concat(rest[0]),tail(rest)))
            :[done]}
    function tail(a){return a.slice(1)}
}

Thanks

Leave a response

Note: some MarkDown is allowed, but HTML is not. Expand to show what's available.

•  Emphasize with italics: surround word with underscores _emphasis_
•  Emphasize strongly: surround word with double-asterisks **strong**
•  Link: surround text with square brackets, url with parentheses [text](url)
•  Inline code: surround text with backticks `IEnumerable`
•  Unordered list: start each line with an asterisk, space * an item
•  Ordered list: start each line with a digit, period, space 1. an item
•  Insert code block: start each line with four spaces
•  Insert blockquote: start each line with right-angle-bracket, space > Now is the time...

Name (required) Mail (will not be published) (required) Website Response Submit

Preview of response