3
\$\begingroup\$

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

Thanks in advance for any help!

\$\endgroup\$
  • 1
    \$\begingroup\$ 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). \$\endgroup\$ – Kruga Sep 14 '17 at 11:47
  • \$\begingroup\$ 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) \$\endgroup\$ – wOxxOm Sep 14 '17 at 17:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.