Generate unique combinations in JavaScript from n objects with r samples

user_8147508 0
Viewed 383

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?

node.js arrays javascript
3 Answers

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.

user_9891210

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);

user_45432070

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.

user_22121280
Related