5
\$\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 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;
}
\$\endgroup\$
2
  • 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, 2017 at 11:47
  • 1
    \$\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, 2017 at 17:29

1 Answer 1

1
\$\begingroup\$

Remarks

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

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.