perms_recursive_instrumented.js

const permutations = array => {
  console.log("in", array)
  if (array.length < 2) {
    // Base case, return single-element array wrapped in another array
    console.log("out", [array])
    return [array];
  } else {
    let perms = [];
    for (let index = 0; index < array.length; index++) {
      // Make a fresh copy of the passed array and remove the current element from it
      let rest = array.slice();
      rest.splice(index, 1);
 
      // Call our function on that sub-array, storing the result: an array of arrays
      let ps = permutations(rest);

      // Add the current element to the beginning of each sub-array and add the new
      // permutation to the output array
      const current = [array[index]]
      for (let p of ps) {
        perms.push(current.concat(p);
      }
    });
    console.log("out", perms)
    return perms;
  }
};

permutations([1, 2, 3, 4]);

/*
in [ 1, 2, 3, 4 ]
in [ 2, 3, 4 ]
in [ 3, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 3 ]
out [ [ 3 ] ]
out [ [ 3, 4 ], [ 4, 3 ] ]
in [ 2, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 2 ]
out [ [ 2 ] ]
out [ [ 2, 4 ], [ 4, 2 ] ]
in [ 2, 3 ]
in [ 3 ]
out [ [ 3 ] ]
in [ 2 ]
out [ [ 2 ] ]
out [ [ 2, 3 ], [ 3, 2 ] ]
out [ [ 2, 3, 4 ],
  [ 2, 4, 3 ],
  [ 3, 2, 4 ],
  [ 3, 4, 2 ],
  [ 4, 2, 3 ],
  [ 4, 3, 2 ] ]
in [ 1, 3, 4 ]
in [ 3, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 3 ]
out [ [ 3 ] ]
out [ [ 3, 4 ], [ 4, 3 ] ]
in [ 1, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 4 ], [ 4, 1 ] ]
in [ 1, 3 ]
in [ 3 ]
out [ [ 3 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 3 ], [ 3, 1 ] ]
out [ [ 1, 3, 4 ],
  [ 1, 4, 3 ],
  [ 3, 1, 4 ],
  [ 3, 4, 1 ],
  [ 4, 1, 3 ],
  [ 4, 3, 1 ] ]
in [ 1, 2, 4 ]
in [ 2, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 2 ]
out [ [ 2 ] ]
out [ [ 2, 4 ], [ 4, 2 ] ]
in [ 1, 4 ]
in [ 4 ]
out [ [ 4 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 4 ], [ 4, 1 ] ]
in [ 1, 2 ]
in [ 2 ]
out [ [ 2 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 2 ], [ 2, 1 ] ]
out [ [ 1, 2, 4 ],
  [ 1, 4, 2 ],
  [ 2, 1, 4 ],
  [ 2, 4, 1 ],
  [ 4, 1, 2 ],
  [ 4, 2, 1 ] ]
in [ 1, 2, 3 ]
in [ 2, 3 ]
in [ 3 ]
out [ [ 3 ] ]
in [ 2 ]
out [ [ 2 ] ]
out [ [ 2, 3 ], [ 3, 2 ] ]
in [ 1, 3 ]
in [ 3 ]
out [ [ 3 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 3 ], [ 3, 1 ] ]
in [ 1, 2 ]
in [ 2 ]
out [ [ 2 ] ]
in [ 1 ]
out [ [ 1 ] ]
out [ [ 1, 2 ], [ 2, 1 ] ]
out [ [ 1, 2, 3 ],
  [ 1, 3, 2 ],
  [ 2, 1, 3 ],
  [ 2, 3, 1 ],
  [ 3, 1, 2 ],
  [ 3, 2, 1 ] ]
out [ [ 1, 2, 3, 4 ],
  [ 1, 2, 4, 3 ],
  [ 1, 3, 2, 4 ],
  [ 1, 3, 4, 2 ],
  [ 1, 4, 2, 3 ],
  [ 1, 4, 3, 2 ],
  [ 2, 1, 3, 4 ],
  [ 2, 1, 4, 3 ],
  [ 2, 3, 1, 4 ],
  [ 2, 3, 4, 1 ],
  [ 2, 4, 1, 3 ],
  [ 2, 4, 3, 1 ],
  [ 3, 1, 2, 4 ],
  [ 3, 1, 4, 2 ],
  [ 3, 2, 1, 4 ],
  [ 3, 2, 4, 1 ],
  [ 3, 4, 1, 2 ],
  [ 3, 4, 2, 1 ],
  [ 4, 1, 2, 3 ],
  [ 4, 1, 3, 2 ],
  [ 4, 2, 1, 3 ],
  [ 4, 2, 3, 1 ],
  [ 4, 3, 1, 2 ],
  [ 4, 3, 2, 1 ] ]
 */