how to get all permutations of a set in javascript

To get all the permutations of a set in javascript, you can use a recursive algorithm. Here's one way to implement it:

index.tsx
function getPermutations(array) {
  const permutations = [];

  function swap(a, b) {
    const temp = array[a];
    array[a] = array[b];
    array[b] = temp;
  }

  function generate(n) {
    if (n === 1) {
      permutations.push([...array]);
    } else {
      for (let i = 0; i < n; i++) {
        generate(n - 1);
        swap(n % 2 ? 0 : i, n - 1);
      }
    }
  }

  generate(array.length);
  return permutations;
}
425 chars
24 lines

Here's how it works:

  • The getPermutations function takes an array as input and returns an array of all permutations.
  • Inside the function, we declare an empty array called permutations to store the results.
  • We also declare a helper function swap to swap two elements in the array.
  • The main logic happens in the generate function, which takes an integer n as input.
  • If n is 1, we have generated a permutation, so we push a copy of the array to permutations.
  • Otherwise, we need to generate permutations for the first n-1 elements of the array.
  • We do this by recursively calling generate(n-1).
  • We then swap the nth element with one of the first n-1 elements, and repeat the process for the remaining n-1 elements.
  • The swap function uses the modulo operator to alternate between swapping the first element and the i-th element for even and odd values of n.
  • Finally, we call generate with the length of the input array and return the permutations array.

Here's an example usage:

index.tsx
const array = ['a', 'b', 'c'];
const permutations = getPermutations(array);
console.log(permutations);
103 chars
4 lines

This will output the following array:

index.tsx
[
  [ 'a', 'b', 'c' ],
  [ 'b', 'a', 'c' ],
  [ 'c', 'a', 'b' ],
  [ 'a', 'c', 'b' ],
  [ 'b', 'c', 'a' ],
  [ 'c', 'b', 'a' ]
]
129 chars
9 lines

gistlibby LogSnag