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
  }
}

Behavior

• It generates an array of given candidates having length n for each generation.
• Every arrays are indendent i.e. has different reference. But same element between arrays have equal reference, so be careful.
• When length is equal or less than 0, it does nothing.
• Order of the candidates follow lexiographical order, based on given candidates order.

const list = [...combinateWithReplacement([0, 1, 2], 2)]

/*
  list === [
    [0, 0],
    [0, 1],
    [0, 2],
    [1, 0],
    [1, 1],
    [1, 2],
    [2, 0],
    [2, 1],
    [2, 2],
  ]
*/

Example

Consider someone want's to find a combination of n numbers in finite set(ex: { 1, 3, 5, 7 }), which sum of squares is any arbitrary integer x. Multiple uses of a single number is allowed. This brute force algorithm will help them.

function solve(list: number[], n: number, x: number) {
  for (const candidate of combinateWithReplacement(list, n)) {
    if (candidate.reduce((acc, value) => acc + value ** 2, 0) === x) {
      return candidate
    }
  }
  return undefined
}

console.log(solve([1, 3, 5, 7], 5, 157)) // [1, 3, 7, 7, 7]
console.log(solve([1, 3, 5, 7], 5, 134)) // undefined

How does it work

Basically it iterates candidates.length-ary numbers with length digits, and take each digit as index for each element.

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)
}