3
\$\begingroup\$

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?

\$\endgroup\$
2
\$\begingroup\$

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 you should be able to tweak it to be a generator function.

\$\endgroup\$
2
\$\begingroup\$

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);

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.