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?
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.
The following recursive code should be efficient. You can perhaps make it mode efficient in JS if you rephrase it into imperative loops etc.
C 17/10 is done @30ms on an old AMD Phenom 1090T whereas C25/10 takes about 1500ms.
function getCombinations(a,n,s=[],t=[]){
return a.reduce((p,c,i,a) => ( n > 1 ? getCombinations(a.slice(i+1), n-1, p, (t.push(c),t))
: p.push((t.push(c),t).slice(0))
, t.pop()
, p
),s)
}
var a = Array.from({length:25}, (_,i) => i),
n = 10,
c;
console.time("cs");
c = getCombinations(a,n);
console.timeEnd("cs");
console.log(c.length);
With the help of a hash-table to store all "already visited combinations" in order to avoid recursing multiple times through them, I managed to optimize the recursive algorith to calculate R=10 for a N of size 17 in ~44 seconds.
The problem is that the number of combinations grows by a factorial margin. With N 25 and R 10 we are already looking at something like 15! combinations, which is quite large (1.3076744e+12).
You might have an easier time implementing the algorithm in a faster language/system and delegating computation there.
const N = [100,200,300,400,500,600,700,800,900,1000,1100,1200,1300,1400,1500,1600,1700];
const R = 10;
const hash = (arr) => arr.join('-');
const solutions = [];
const visitedHashes = {};
const uniqueCombos = (n, r) => {
const nHash = hash(n);
if (visitedHashes[nHash]) {
return;
}
visitedHashes[nHash] = true;
if (n.length < r) {
return;
}
else {
if (n.length === r) {
solutions.push(n);
}
n.forEach(element => uniqueCombos(n.filter(el => el !== element), r));
}
}
const start = Date.now();
uniqueCombos(N, R);
const time = Date.now() - start;
console.log(`${solutions.length} combinations calculated in ${time} milliseconds`);EDIT 2: As per Yoshi's comment-suggestion, using a lookup object instead of an array for visitedHashes reduced time significantly.
