Permutations generator

permutations.js

function swap(arr, aIdx, bIdx) {
  if (aIdx < 0 || aIdx >= arr.length) throw new TypeError();
  if (bIdx < 0 || bIdx >= arr.length) throw new TypeError();

  const temp = arr[aIdx];
  arr[aIdx] = arr[bIdx];
  arr[bIdx] = temp;
}

function shiftToEnd(arr, idx) {
  if (idx < 0 || idx >= arr.length) throw new TypeError();

  const toShift = arr[idx]; // 1, 2, 3
  const end = arr.length - 1;
  for (let i = idx; i < end; i++) {
    arr[i] = arr[i + 1];
  }
  arr[arr.length - 1] = toShift;
}

export function permutationsRec(arr, k = arr.length, start = 0, perms = []) {
  if (start === k) {
    perms.push(arr.slice(0, k));
  } else {
    for (let i = start; i < arr.length; i++) {
      swap(arr, start, i);
      permutationsRec(arr, k, start + 1, perms);
    }
    shiftToEnd(arr, start);
  }
  return perms;
}

export function* permutations(arr, k = arr.length) {
  const ist = [0]; // i stack
  let start = 0; // start === ist.length - 1

  while (ist.length > 1 || ist[0] < arr.length) {
    swap(arr, start, start + ist[start]);
    if (ist.length === k) {
      yield arr.slice(0, k);
      ++ist[start];
    } else {
      ist.push(0);
      start++;
    }

    while (ist[start] === arr.length - start) {
      shiftToEnd(arr, start);
      ist.pop();
      start--;
      ist[start]++;
    }
  }
}