Algorithm: Heap Permutation

heap-permutation.js

function permute(arr) {
  const permutations = [];
  function heapPerm(array, size) {
    if (size === 1) {
      permutations.push(array.slice(0));
    }
    for (let i = 0; i < size; i++) {
      const prev = size - 1;
      heapPerm(array, prev);
      if (size % 2 === 0) {
        [ array[0], array[prev] ] = [ array[prev], array[0] ]
      } else {
        [ array[i], array[prev] ] = [ array[prev], array[i] ]
      }
    }
  }
  heapPerm(arr, arr.length);
  return permutations;
}

/*
console.log(permute([1, 2, 3]));
[
  [1, 2, 3],
  [2, 1, 3],
  [3, 2, 1],
  [2, 3, 1],
  [3, 1, 2],
  [1, 3, 2]
]
*/