Heap's algorithm implementation - permutations

Question

I wrote an implementation of Heap's permutation algorithm in JavaScript (ES2015):

const swap = (array, pos1, pos2) => {
  const temp = array[pos1];

  array[pos1] = array[pos2];
  array[pos2] = temp;
}

const heapsPermute = (() => {
  const result = [];

  return (array, n = array.length) => {
    const newArray = typeof array === 'string'
      ? array.split('')
      : array;

    if (n === 1)
      result.push(newArray.join(''));

    for (let i = 1; i <= n; i++) {
      heapsPermute(newArray, n - 1);

      const j = n % 2
        ? 0
        : i - 1;

      swap(newArray, j, n - 1);
    }

    return result;
  };
})();

console.log(heapsPermute('abcdef').length);

It should take an array|string argument and return array of strings with all permutations.

What do you think about it. Is there room for improvement anywhere?

Answer 1

It should take an array|string argument and return array of strings with all permutations.

Why flatten each permutation to a string? That's a major limitation to the usefulness. If you're justifying it by YAGNI then that's fair enough, but I don't see that explicitly stated anywhere. And I'm not sure it's entirely justified here anyway, because the change doesn't overcomplicate the code. It's just replacing

      result.push(newArray.join(''));

with

      result.push(newArray.slice());

---

Why return all of the permutations in a single array? There are \$n!\$ permutations of \$n\$ elements, so available memory quickly becomes a limiting factor. I would consider looping over \$12!\$ elements, but I wouldn't want to put them in an array. Since the question is tagged ecmascript-6 you should be able to tweak it to be a generator function.

Answer 2

From a short review:

• Keep the typeof check out of the recursive part, you only need to do this during the first call of the function
• The fat arrow syntax is good for inline functions, in this case I would highly encourage you to use the function keyword
• If nis 1, get out of the function after the push, there is no need to execute the remainder
• I like verbThing for naming function, so perhaps use swapListElements and permutateList permuteList
• "heap" is not a JavaScript thing, I would not use it in your naming unless you actually created a "Heap" object
• newArray is not a great name, especially since most of the time it is not actually a new array, but the array that was passed to the function
• I had to re-read the code that uses j, the variable is not intuitively named, and the code could use a comment there
• Furthermore, the ternary statements over 3 lines are mind breaking, I would keep them on 1 line

This is my version of Heap's algorithm, with the above taken into account

function swap(list, pos1, pos2){
  const temp = list[pos1];
  list[pos1] = list[pos2];
  list[pos2] = temp;
}

//Implements Heap's permutation algorithm
//https://en.wikipedia.org/wiki/Heap%27s_algorithm
function permute(list) {

  var out = [];
  list = typeof list === 'string' ? list.split('') : list;
  permuteList(list, list.length);

  function permuteList(list, n) {
    var i;

    if (n == 1) {
      out.push(list.join(''));
    } else {
      for (i = 0; i < n - 1; i++) {
        permuteList(list, n - 1);
        if (n % 2) {
          swap(list,0, n - 1);
        } else {
          swap(list,i, n - 1);
        }
      }
      permuteList(list, n - 1);
    }
  }
  return out;
}

console.log(permute('abc'));
console.log(permute('abcdef').length);