Permutation on the large array (Javascript)

Hai Nguyễn Van 0
Viewed 26

I have a simple permute function. It works well with arrays that have less than 5 items. But when I have 40 items in the array, my web is crashed. I used to try to split that large array into small sub-arrays, but it missed many cases. Are there other ways to solve this problem?

const permute = (items) => {
  const result = [];
  const dsf = (i, items) => {
    if (i === items.length) {
      result.push(items.slice())
      return;
    }

    for (let j = 0; j < items.length; j++) {
      [items[i], items[j]] = [items[j], items[i]];
      dsf(i + 1, items);
      [items[i], items[j]] = [items[j], items[i]];
    }
  }
  dsf(0, items);
  return result;
}
permute crash performance recursion javascript
1 Answers

815,915,283,247,897,734,345,611,269,596,115,894,272,000,000,000

The number of permutations given N elements is N!. So with 40 elements you would have 8.1591528e+47 permutations. Calculations of this magnitude are completely impractical on pretty much any regular machine.

Also, the code you attached doesn't calculate the permutations correctly since theres are a few duplicates in the output.

Here is a better way to calculate permutations.

function permute(arr) {
   const res = [];
   if (arr.length === 0) return [];
   if (arr.length === 1) return [arr];
   for (let i = 0; i < arr.length; i++) {
      const cur = arr[i];
      const remaining = arr.slice(0, i).concat(arr.slice(i + 1));
      const permutations = permute(remaining);
      for (let j = 0; j < permutations.length; j++) {
         const permuted = [cur].concat(permutations[j]);
         res.push(permuted);
      }
   }
   return res;
}
Fweej050
Related