# Recursive JavaScript Permutations Function

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 it's 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])
.concat(sublist.slice(pos, sublist.length)));
}
}
return permutations;
}


Thanks in advance for any help!

• 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). – Kruga Sep 14 '17 at 11:47
• 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); permutations.push(copy) -- and of course don't enumerate arrays via in, use for (const sublist of subpermutations) – wOxxOm Sep 14 '17 at 17:29