javascript - 在 JavaScript 中从 n 个对象和 r 个样本生成唯一的组合

Question

从带有 R 样本的 N 个对象中生成 JavaScript 中所有唯一组合的最佳方法是什么。例如:

n = [100,200,300,400]
r = 3

预期结果

    [100,200,300]
    [100,200,400]
    [200,300,400]
    [100,300,400]

我能够使用递归解决方案实现上述目标。但对于大型数据集(例如N=25，R=10)来说速度很慢。有没有更快的方法来实现这一目标？

Answer 1

好的，这里是维基百科中描述的顺序生成器的直接实现:

...track k index numbers of the elements selected, starting with {0 .. k−1} (zero-based) or {1 .. k} (one-based) as the first allowed k-combination and then repeatedly moving to the next allowed k-combination by incrementing the last index number if it is lower than n-1 (zero-based) or n (one-based) or the last index number x that is less than the index number following it minus one if such an index exists and resetting the index numbers after x to {x+1, x+2, …}. https://en.wikipedia.org/wiki/Combination#Enumerating_k-combinations

function combinations(a, c) {
    let index = []
    let n = a.length

    for (let j = 0; j < c; j++)
        index[j] = j
    index[c] = n

    let ok = true
    let result = []

    while (ok) {

        let comb = []
        for (let j = 0; j < c; j++)
            comb[j] = a[index[j]]
        result.push(comb)

        ok = false

        for (let j = c; j > 0; j--) {
            if (index[j - 1] < index[j] - 1) {
                index[j - 1]++
                for (let k = j; k < c; k++)
                    index[k] = index[k - 1] + 1
                ok = true
                break
            }
        }
    }

    return result
}

//

N = 25
R = 10
A = Array(N).fill(0).map((_, n) => n)

console.time()
combs = combinations(A, R)
console.log(combs.length, 'combinations')
console.timeEnd()

在我的机器上花费 < 1 秒。