Recursive Array Permutations in JavaScript

Introduction

In this lab, we will explore the concept of array permutations in JavaScript. We will learn how to use recursion to generate all possible permutations of an array's elements, even if they contain duplicates. We will also understand how to use Array methods such as map() and reduce() to combine the different permutations into a single array. However, we must keep in mind that executing this function on arrays with more than 8 to 10 elements may significantly increase the execution time and cause the browser to hang.

Skills Graph

How to Generate All Array Permutations

To start practicing coding, open the Terminal/SSH and type node.

Here's an algorithm that generates all permutations of an array's elements (even if it contains duplicates). Follow these steps to implement it:

1. Use recursion.
2. For each element in the given array, create all the partial permutations for the rest of its elements.
3. Use Array.prototype.map() to combine the element with each partial permutation, then Array.prototype.reduce() to combine all permutations in one array.
4. The base cases are for arrays with a length of 2 or 1.
5. Beware that this function's execution time increases exponentially with each array element. Anything more than 8 to 10 entries may cause your browser to hang as it tries to solve all the different combinations.

Here's the code:

const permutations = (arr) => {
  if (arr.length <= 2) return arr.length === 2 ? [arr, [arr[1], arr[0]]] : arr;
  return arr.reduce(
    (acc, item, i) =>
      acc.concat(
        permutations([...arr.slice(0, i), ...arr.slice(i + 1)]).map((val) => [
          item,
          ...val
        ])
      ),
    []
  );
};

You can test the code by calling the permutations() function with an array argument:

permutations([1, 33, 5]);
// [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]

Summary

Congratulations! You have completed the Array Permutations lab. You can practice more labs in LabEx to improve your skills.