Recursive JavaScript permutations function

Question

I have a recursive function that calculates the permutations of a given list/array list. Although a similar implementation works great in Python, this JavaScript implementation cannot handle a list of more than 7 elements before its webpage kills it.

I realise this is a natural effect of the recursion, but I am only making \$n\$ recursive calls for a list of size \$n\$. Is there any JavaScript performance magic that could be used to save this function, even if only for a handful more cases?

function permute(list) {
 if (list.length == 1) { return [list] }
 let permutations = []
 let subpermutations = permute(list.slice(1, list.length))
 for (index in subpermutations) {
 let sublist = subpermutations[index]
 for (let pos = 0; pos < sublist.length+1; pos++) {
 permutations.push(sublist.slice(0, pos)
 .concat([list[0]])
 .concat(sublist.slice(pos, sublist.length)));
 }
 }
 return permutations;
}

• Kruga: Array manipulation is slow, and you have several in your inner loop. That loop runs almost 6000 times for n=7, and over 4 million times for n=10 (my browser dies at n=11).
• woxxom: You should use a better algorithm, but FWIW a 2x speedup of your code may be achieved by using splice on a copy: const copy = sublist.slice(); copy.splice(pos, 0, list[0]); permutations.push(copy) -- and of course don't enumerate arrays via in, use for (const sublist of subpermutations)

Answer 1

Remarks

• The algorithm used seems vastly ineffective (lots of sliceing and concating greatly contributes to it),
• The strict equality operator shall be used in place of the equality operator wherever applicable,
• Use the for...of statement instead of for...in.

Rewrite (ES2015+)

The below rewrite is my implementation of the non-recursive variant of the Heap's algorithm, which might be the most effective algorithm for the job. Another noteworthy one is the "Steinhaus–Johnson–Trotter algorithm", but it's more complicated and less performant in practice.

Please note, many portions of the below code could have been written in a far more idiomatic way, e.g. the swap function could have been completely replaced with a destructuring assignment which is far more concise, but that would come at a price of performance, which in this case is a critical point.

const permute = arr => {
 const permutations = [];
 const swap = (a, b) => {
 const tmp = arr[a];
 arr[a] = arr[b];
 arr[b] = tmp;
 };
 const c = new Array(arr.length).fill(0);
 permutations.push(arr.slice());
 let i = 0;
 while (i < arr.length) {
 if (c[i] < i) {
 swap(i, i % 2 ? c[i] : 0);
 permutations.push(arr.slice());
 c[i] += 1;
 i = 0;
 }
 else {
 c[i] = 0;
 i += 1;
 }
 }
 return permutations;
};

Benchmark

The times change, try it yourself!

• Original ― 69,330.36 ops/s ± 1.05% (93.9% slower)
• The above implementation ― 1,135,764.38 ops/s ±2.29% (fastest)

Permutation solutions benchmark