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;
}
splice
on a copy: const copy = sublist.slice(); copy.splice(pos, 0, list[0]); permutations.push(copy) -- and of course don't enumerate arrays viain
, use for (const sublist of subpermutations) \$\endgroup\$