Skip to content

Generate unique combinations in JavaScript from n objects with r samples

What is the best way to generate all unique combinations in JavaScript from N objects with R samples. For example:

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

Expected result

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

I am able to achieve above using recursive solution. But it is slow for large datasets (e.g. N=25, R=10). Is there any faster way to achieve this?

Answer

Ok, here a straight implementation of a sequential generator as described in Wikipedia:

…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()

Takes < 1 sec on my machine.