Last active
January 17, 2024 09:29
-
-
Save Phryxia/a1cfe513d0611a8e6f5ebf205583c816 to your computer and use it in GitHub Desktop.
TypeScript implementation of combination with replacement of given elements with arbitrary length.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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)
}
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Behavior
candidates
having lengthn
for each generation.length
is equal or less than0
, it does nothing.candidates
order.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 integerx
. Multiple uses of a single number is allowed. This brute force algorithm will help them.How does it work
Basically it iterates
candidates.length
-ary numbers withlength
digits, and take each digit as index for each element.