Generate a set of combinations

Question

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"

Answer 1

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