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.