TypeScript implementation of combination with replacement of given elements with arbitrary length.

combinateWithReplacement.ts

export function* combinateWithReplacement<T>(candidates: T[], length: number) {
  if (length <= 0) return
  
  for (let i = 0; i < candidates.length ** length; ++i) {
    const result = new Array<T>(length)
    let j = i
    for (let k = length - 1; k >= 0; --k) {
      result[k] = candidates[j % candidates.length]
      j = Math.floor(j / candidates.length)
    }
    yield result
  }
}

Here is another, more intuitive recursion based algorithm. But it turns out that its performance is significantly worse. #jsben.ch

This is because of recursion which have function call overload.

export function* combinateWithReplacement<T>(candidates: T[], length: number) {
  const placeholder: T[] = new Array(length)

  function* recurse(depth: number): Generator<T[]> {
    if (depth >= length) {
      yield placeholder.slice()
      return
    }

    for (const candidate of candidates) {
      placeholder[depth] = candidate
      yield* recurse(depth + 1)
    }
  }

  yield* recurse(0)
}