How to Generate Permutations in JavaScript

1. Permutation of a Given Array
2. Permutation on a Given String

In JavaScript, there is slice, reduce, filter, substring, and many more methods to ease out the base problem of permutating all possible trials of a given string or array.

Here, we will show how to draw out the combination of arrays and strings from a given input. The main focus is to divide each literal from the array or string and swap other literals one by one.

In the following sections, we will be discussing the procedure in detail with necessary code examples.

Permutation of a Given Array

We will initialize a function permute with another function backtrack within it. This function backtrack will be recursively called for executing the proper set of combinations.

Code Snippet:

var permute = function(nums) {
  var result = [];
  var backtrack = (i, nums) => {
    if (i === nums.length) {
      result.push(nums.slice());
      return;
    }
    for (let j = i; j < nums.length; j++) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      backtrack(i + 1, nums);
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  } backtrack(0, nums);
  console.log(result);
  return result;
};
permute([1, 2, 3]);

Output:

The major action here defines the swapping portion, where we swap each literal with one another of one trial (e.g. [1,2,3]) and bring out the probable combinations.

From the trial [1,2,3], we will get [1,2,3] & [1,3,2]. This portion will be executed until every literal gets a check.

Before switching to the next trial, we returned to the base trial (1,2,3) by swapping again (as the last combination was [1,3,2]). It is how the backtracking is operated.

A tree is formed to see the possible trials, and the tree length is equal to the array length. Initially, we perform a DFS for solving the case, and the recursive backtracking procedure does it.

Permutation on a Given String

In the case of a string, we will split the string first, and then we will use the reduce method to concat the probable trials one by one by recursively calling the permutationString function.

Code Snippet:

var permutationString = str => {
  if (str.length <= 2)
    return str.length === 2 ? [str[0] + str[1], str[1] + str[0]] : [str];
  return str.split('').reduce(
      (accumulator, letter, i) => accumulator.concat(
          permutationString(str.slice(0, i) + str.slice(i + 1))
              .map(val => letter + val)),
      []);
};
console.log(permutationString('abcd'));

Output:

According to the accumulator function, we are preserving each combination.

We use the slice method to lock a certain alphabet and add the rest of the alphabets as per the base case initialized before. Finally, the output results in the combined form of all expected patterns.

The factorial formulas derive the method permutation, and thus the solution to this problem often meets runtime error for large cases. But the basic inference for the problem with a proper visualization can be directed this way.