Calculate all permutations of a JavaScript array or string
A problem I've struggled with in my earlier days as a developer was generating all permutations of an array's elements or a string's characters. This is a classic problem that can be solved using recursion, even if fairly inefficiently.
Array permutations
Using recursion, we can generate all permutations of an array's elements, including duplicates. The base cases for the recursive function are when the array's length is equal to 2
or 1
. In this case, we return the array itself or an array with the elements swapped, respectively.
For all other cases, we use Array.prototype.reduce()
to iterate over the array's elements, creating all the partial permutations for the rest of the elements. We then use Array.prototype.map()
to combine the current element with each partial permutation, and Array.prototype.reduce()
to combine all permutations in one array.
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, ]) ), [] ); }; permutations([1, 33, 5]); // [ [1, 33, 5], [1, 5, 33], [33, 1, 5], [33, 5, 1], [5, 1, 33], [5, 33, 1] ]
String permutations
A similar technique can be used for a string. The base cases are identical and the algorithm is generally the same. The only significant difference is the use of String.prototype.split()
to convert the string into an array of characters, and String.prototype.join()
to convert the array of characters back into a string.
const stringPermutations = str => { if (str.length <= 2) return str.length === 2 ? [str, str[1] + str[0]] : [str]; return str .split('') .reduce( (acc, letter, i) => acc.concat( stringPermutations(str.slice(0, i) + str.slice(i + 1)).map( val => letter + val ) ), [] ); }; stringPermutations('abc'); // ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']