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

• Peter Taylor: Two minor points: the verb cognate to permutation is permute; and Heap is the name of the algorithm's inventor.