combinations_with_replacement.ts

function repeat(x: number, n: number): number[] {
  return Array(n).fill(x);
}

/**
 * Reimplemented Python's itertools.combinations_with_replacement
 * https://docs.python.org/3/library/itertools.html#itertools.combinations_with_replacement
 */
export function* combinationsWithReplacement<T>(pool: T[], r: number) {
  const n = pool.length;
  if (!(n && r)) {
    return;
  }

  const indices = repeat(0, r);
  yield indices.map((i) => pool[i]);

  while (true) {
    let cont = false;
    let i = r - 1;
    for (; i >= 0; i--) {
      if (indices[i] !== n - 1) {
        cont = true;
        break;
      }
    }

    if (!cont) {
      return;
    }

    indices.splice(i, r - i, ...repeat(indices[i] + 1, r - i));
    yield indices.map((i) => pool[i]);
  }
}