# Heap's algorithm implementation - permutations

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?

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.

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