How to Generate All Permutations of an Array in JavaScript?

How to Compute Permutations in JavaScript?

Permutations refer to generating all possible sequences from an array. In JavaScript, an array of integers can be permuted using a few different approaches.

Approach with memoization

One approach involves using recursion and memoization to keep track of previously calculated permutations. Here's an implementation:

let permArr = [];
let usedChars = [];

function permute(input) {
  const chars = input.sort();  // Prevent duplicate permutations with identical values

  for (let i = 0; i < chars.length; i++) {
    const ch = chars.splice(i, 1);
    usedChars.push(ch);
    if (chars.length === 0) {
      permArr[permArr.length] = usedChars.join("");
    }
    permute(chars.join(""));
    chars.splice(i, 0, ch);
    usedChars.pop();
  }

  return permArr;
}

Approach with non-mutating array

Another approach uses a non-mutating slicing technique to avoid altering the original array:

function permutator(inputArr) {
  let result = [];

  function permute(arr, memo = []) {
    if (arr.length === 0) {
      result.push(memo);
    } else {
      for (let i = 0; i < arr.length; i++) {
        permute(arr.slice(0, i).concat(arr.slice(i + 1)), memo.concat(arr[i]));
      }
    }
  }

  permute(inputArr);

  return result;
}

ES6 version

An ES6 implementation of the non-mutating approach:

const permutator = (inputArr) => {
  let result = [];

  const permute = (arr, m = []) => {
    if (arr.length === 0) {
      result.push(m);
    } else {
      for (let i = 0; i < arr.length; i++) {
        let curr = arr.slice();
        let next = curr.splice(i, 1);
        permute(curr.slice(), m.concat(next));
      }
    }
  };

  permute(inputArr);

  return result;
};

Sample Input and Output

For example, with the following input array:

[1, 2, 3]

The permutation functions will output:

[
  [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ]
]

These permutations are generated by exploring all possible combinations of the input array elements, ensuring that each element is used exactly once in each permutation.

The above is the detailed content of How to Generate All Permutations of an Array in JavaScript?. For more information, please follow other related articles on the PHP Chinese website!