Skip to content

Instantly share code, notes, and snippets.

@Phryxia
Last active January 17, 2024 09:29
Show Gist options
  • Save Phryxia/a1cfe513d0611a8e6f5ebf205583c816 to your computer and use it in GitHub Desktop.
Save Phryxia/a1cfe513d0611a8e6f5ebf205583c816 to your computer and use it in GitHub Desktop.
TypeScript implementation of combination with replacement of given elements with arbitrary length.
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
}
}
@Phryxia
Copy link
Author

Phryxia commented Jan 17, 2024

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.

@Phryxia
Copy link
Author

Phryxia commented Jan 17, 2024

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment