0
\$\begingroup\$

For one of my personal projects, I needed an algorithm to generate a set of combinations.

I've finally successfully written one.

The problem is that this algorithm uses two recursive calls to generate the combinations, and it takes a lot of time to compute.

I suspect that converting the code into a non-recursive algorithm, using loops, will speed it up, but anything that improves performance will be helpful.

Here is my code and some details to give you an example:

/** get all combinations of `outSize` over (combinations of `elemsSize` over `inSet`) 
 * minFrst is for recursion use only
**/
function* genCombinations2(inSet, outSize, elemsSize, minFrst) {
  if(outSize<=0)
    return;

  const tCn = genCombinations1(inSet,elemsSize);
  --outSize; // because comparing with 1 and using value -1 in following

  for(let c of tCn) {
    if(minFrst && c[0] < minFrst)
      continue;
    else if(outSize === 0)
      yield [c];
    else {
      const subset = []; // inSet \ elems of c
      for(let i=0; i<inSet.length; i++)
        if(c.indexOf(inSet[i])<0)
          subset[subset.length] = inSet[i];

      for(let rep of genCombinations2(subset, outSize, elemsSize, c[0]+1)) { // I want to eliminate this <<<<<<<<<<<<<<<<<<
        rep[rep.length] = c;
        yield rep;
      }
    }
  }
}

/** get all combinations of `outSize` over `inSet`
 * max is for recursion use only
**/
function* genCombinations1(inSet, outSize, max) {
  max++;
  if(outSize<=0)
    return;
  else if(--outSize === 0)
    for(let i=0; i<(max || inSet.length); i++)
      yield [inSet[i]];

  else {
    for(let i=outSize; i<(max || inSet.length); i++) {
      for(let rep of genCombinations1(inSet, outSize, i-1)) { // I want to eliminate this <<<<<<<<<<<<<<<<<<<<<<
        rep[rep.length] = inSet[i];
        yield rep;
      }
    }
  }
}

let z = 0;
console.time('genCombinations2(5,2,2)');
for(let a of genCombinations2([0,1,2,3,4],2,2)) z++;
console.timeEnd('genCombinations2(5,2,2)');
console.log('z=',z,'/15');
z = 0;
console.time('genCombinations2(10,4,2)');
for(let a of genCombinations2([0,1,2,3,4,5,6,7,8,9],4,2)) z++;
console.timeEnd('genCombinations2(10,4,2)');
console.log('z=',z,'/4725');

Current details of implementation (can be changed, it is just how I made this works for now):

  • "genCombinations1" significate "generator of all combinations on 1 dimension" and "genCombinations2" is for "generator of all combinations of 2 dimensions"
  • In genCombinations1, elements in the output set are sorted.
  • In genCombinations2, elements in the output set are sorted by the first subelement ([0,...] will be first, [1,...] second etc...).

Exemples of uses (for current implementation):

genCombinations2([0,1,2,3,4,5,6], 3, 2); should yield:
 [[0,1],[2,3],[4,5]]
 [[0,1],[2,3],[4,6]]
 [[0,1],[2,3],[5,6]]
 [[0,1],[2,4],[5,6]]
 [[0,1],[2,5],[4,6]]
 [[0,1],[2,6],[4,5]]
 [[0,1],[3,4],[5,6]]
 ...
 [[1,2],[3,4],[5,6]]

genCombinations1([0,1,2,3,4], 4); should yield:
 [0,1,2,3]
 [0,1,2,4]
 [0,1,3,4]
 [0,2,3,4]
 [1,2,3,4]

Constraints (should not be changed):

  • I don't want to generate all combinations and store them to an array before using them (sometimes my software will ask for combinations over more than 20 elements, that make more than 102,866,828,839 combinations so DO NOT store them all in an array)
  • I my need that the function genCombinations2 is a generator; to that algorithm that use it can gather values progressively (we can (should ?) convert genCombinations1 to an iterative function if possible to improve performances)
  • genCombinations1 output should never contains 2 (or more) times the same element ([...,4,...,4,...] is not accepted); 0 times is allowed.
  • genCombinations2 output should not have 2 (or more) subsets containing the same subelement ([[...,4,...],[...,4,...]] is illegal as 4 is present more than 1 time in the output).; an element does not have to be present.
  • genCombinations1 must not yield the same output set more than once, but all combinations should be yielded.
  • genCombinations2 must not yield the same output set more than once, but all combinations should been yield (note that [[1,2],[3,4]] is the same subset as [[2,1],[4,3]] and [[3,4],[1,2]] ...).
  • I work with Javascript (ES6) WITHOUT libraries. This program is for own learning and not for any commercial purposes; so I want to create my own code solution and not use someone else's a magical "black box"
\$\endgroup\$
  • 2
    \$\begingroup\$ Do you want a review of any and all of your code, or do you want us to only say if there's a way to change from a generator to a loop? \$\endgroup\$ – Peilonrayz Jan 16 '18 at 10:54
  • \$\begingroup\$ I rewritten the problem to a simplified version of my code. Reviewing this example without the recursion will be useful for me. \$\endgroup\$ – NatNgs Jan 16 '18 at 14:12
  • \$\begingroup\$ Can you provide actual code, thisGenerator and otherGenerator look like example code. You're too focused on constant optimisations, \$O(1)\$, where you should focus on changing from linier to constant. \$O(n)\$ to \$O(1)\$. Worring about constans is un-needed most of the time, and leads to situations where people think C is the best tool for everything. \$\endgroup\$ – Peilonrayz Jan 16 '18 at 14:49
  • \$\begingroup\$ Ok so let's check my actual code so ! I don't really now what you want to see inside it but ok.. My problem is still to rewrite the genCombinations2 function to not being recursive anymore (like genCombinations1 that is not recursive) \$\endgroup\$ – NatNgs Jan 16 '18 at 15:30
  • 1
    \$\begingroup\$ Combinatorial Generation by Ruskey, section 5.10 seems to be what you're looking for. \$\endgroup\$ – Peter Taylor Jan 18 '18 at 12:19
1
\$\begingroup\$

I highly recommend that you make two public functions, that return different data. I would also not name a public function genCombinations2, instead use combinations.

You should make the combinations function work the way your code does when elemsSize = undefined. As handeling the elemsSize should be a different problem.

And so you'd have:

function* combinations(pool, r) {}

From this, you want to group your values. This is two loops over your data:

function* combinationGroups(pool, size, elementsSize) {
  for (combination of combinations(pool, size * elementsSize)) {
    let ret = [];
    for (let start=0; start < combinations.length; start += elements_size) {
      ret.push(combination.slice(start, start+elementsSize));
    }
    yield ret;
  }
}

And so you just need to think of a way to create combinations. One way could be to do the same as Python's itertools.combinations: (Note the following isn't tested.)

function* combinations(pool, r) {
  const n = pool.length;
  if (r > n) {
    return
  }

  let indices = [...Array(r).keys()];
  function ret() {
    let ret = [];
    for (let i=0; i < indices.length; i++) {
      ret.push(pool[indices[i]])
    }
    return ret;
  }
  yield ret();
  while (true) {
    let broken = false;
    let i = r-1;
    for (; i >= 0; i--) {
      if (indices[i] != i + n - r) {
        broken = true;
        break;
      }
    }
    if (!broken) {
      return;
    }
    indices[i]++;
    for (let j=i+1; j < r; j++) {
      indices[j] = indices[j-1] + 1;
    }
    yield ret();
  }
}
\$\endgroup\$
  • \$\begingroup\$ There is a problem with the function you propose: For example if we call combinationGroup([0,1,2,3],2,2) we will have: [ [0,1],[2,3] ] as only output; but result should have also [ [0,2],[1,3] ] and [ [0,3],[1,2] ]. Maybe look at another question relative to the number of result I should have with this algorithm on MathOverflow - Concerning your combinations method, it works well, but look much more complicated than mine genCombinations1 \$\endgroup\$ – NatNgs Jan 18 '18 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.