Permutations in JavaScript

perms.js

/**
 * The main thing to see here is the 'optimal substructure' i.e.
 * perms([1, 2, 3]) could benefit from first knowing the result of
 * perms([1, 2]), which in turn could use perms([1]) as a starting point
 * and our basest of cases would be perms([]) at which point we have a
 * trivial problem (so was perms([1]) but I like to accoutn for empty).
 *
 * This points us to a helper function we are going to need, spread.
 * spread will 'spread' a single value into all possible array positions
 * at the previous level. So our logic is something like:
 *
 * perms([1, 2, 3])
 * spread([], 1) = [[1]]
 * spread([[1]], 2) = [[2,1], [1, 2]]
 * spread([[2,1], [1, 2]], 3) = [[3, 2, 1], [2, 3, 1], [2, 1, 3], [3, 1, 2], [1, 3, 2], [1, 2, 3]]
 * done!
 *
 * To accomplish this we are going to use a useful function in the JS standard library for Arrays
 * #Array.splice(positionToInsert, numElementToDelete, elemToInsert)
 * it reads a little oddly, but this is an easy way JS provides to insert elements into
 * an array (in-place) and it handles the bookkeeping logic of pushing everything
 * to the right over. So:
 *
 * const arr = [1, 2, 4];
 * arr.splice(2, 0, 3); // at index 2, delete 0 elems, insert 3
 * console.log(arr); [1, 2, 3, 4]
 *
 * Ok, now let's put it all together
 */

// spread a single item throughout an array in all available spots
const spread = (prevPerms, elem) => {
  // base case, no prevPerms
  if (prevPerms.length === 0) {
    return [[elem]];
  }

  const nextPerms = [];

  for (const prevPerm of prevPerms) {
    for (let i = 0; i <= prevPerm.length; i++) {
      const newPerm = [...prevPerm];
      newPerm.splice(i, 0, elem);
      nextPerms.push(newPerm);
    }
  }

  return nextPerms;
};

const permute = (arr) => {
  let permutations = [];

  for (const elem of arr) {
    permutations = spread(permutations, elem);
  }

  return permutations;
};

// I chose the spread parameter order purposefully because ...
// (reduce really is a powerdful concept)
const permuteReduce = (arr) => arr.reduce(spread, []);

// console.log(permute([]));
// console.log(permute([1]));
// console.log(permute([1, 2]));
// console.log(permute([1, 2, 3]));
// console.log(permute(["a", "b", "c"]));
// console.log(permuteReduce([1, 2, 3]));