/** 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 breakeliminate 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 breakeliminate 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');

For one of my personal projects, I had to make an algo to generate set of combinations.
I've finally succeed to get one.
The problem is that this algorithm uses two recursive generators; that takes a lot of time to compute.

I suspect there is a way to convert this into a non-recursive algorithm (that will be certainly faster).

So, I will not ask you to rewrite my code (but if you want, I will let you do :D).

What I need is: How to break this recursive generator into something like using loops ?

/** 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 break 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 break 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');

Constaints (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 ?) break genCombinations1 to a classical functions 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 can be not present.
• genCombinations1 cannot yields 2 times the same output set, but all combinations should been yield.
• genCombinations2 cannot yields 2 times the same output set, 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 find a code solution and not magical token that will do things :P

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.

/** 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');

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"

/** 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 break 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 break 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');

What I need is: How to break this recursive generator into something like using loops ?

Here is my code:(my problem is so to rewrite genCombinations2 to not have recursion anymore)

function* genCombinations2(inSet, outSize, elemsSize, minFrst) {
 if(outSize<=0)
 return;
 --outSize;
 for(let c of genCombinations1(inSet,elemsSize)) {
 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)) {
 rep[rep.length] = c;
  yield rep;
 }
 }
 }
}

/** genCombinations1([0,1,2,3,4], 4); 
 * will yield: [0,1,2,3]; [0,1,2,4]; [0,1,3,4]; [0,2,3,4]; [1,2,3,4]
**/
function* genCombinations1(inSet, outSize) {
 if(inSet.length < outSize)
 return;
 
 const out = [];
 for(let i=0; i<outSize; i++)
 out[i] = i;
 // init [0,1,2,3,..,outSize-1]
 
 const maxLast = inSet.length-outSize;
 while(true) {
 { const yld = [];
  for(let i=0; i<outSize; i++)
 yld[i] = inSet[out[i]];
  yield yld;
 }
 out[outSize-1]++;
 // i= v > i= v
 // (of 0,1,2,3,4,5) out=[0,1,4,6] > out=[0,2,5,6]
 let i;
 for(i=outSize-1; i>0; i--) {
 if(out[i] <= maxLast+i)
 break;
 out[i-1]++;
 }
 if(i===0 && out[i] > maxLast)
 return;
 
 // i= v > i= v
 // (of 0,1,2,3,4,5) out=[0,2,5,6] > out=[0,2,3,4]
 for(i++;i<outSize;i++)
 out[i] = out[i-1]+1;
 }
}

Thank you for help

So, I will not ask you to rewrite my code (but if you want, I will let you do :D).

What I need is: How to break this recursive generator into something like using loops ?

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 break 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 break 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]

Constaints (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 ?) break genCombinations1 to a classical functions 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 can be not present.
• genCombinations1 cannot yields 2 times the same output set, but all combinations should been yield.
• genCombinations2 cannot yields 2 times the same output set, 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 find a code solution and not magical token that will do things :P

Here is a code to give you an example of what I mean: (Can you rewrite this code to have something not recursive ?)

function* thisGenerator(param) {
 const otherGenerator = anotherGenerator(param);
 for(let value of otherGenerator) {
 if(param === 0) {
 yield [value];
 }
 for(let recursion of thisGenerator(param-1)) { // this to not recurse through thisGenerator
 recursion[recursion.length] = value;
 yield recursion;
 }
 }
}

Here is my code: (my problem is so to rewrite genCombinations2 to not have recursion anymore)

function* genCombinations2(inSet, outSize, elemsSize, minFrst) {
 if(outSize<=0)
  return;
 --outSize;
 for(let c of genCombinations1(inSet,elemsSize)) {
 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)) {
 rep[rep.length] = c;
 yield rep;
  }
 }
 }
}
/** genCombinations1([0,1,2,3,4], 4); 
 * will yield: [0,1,2,3]; [0,1,2,4]; [0,1,3,4]; [0,2,3,4]; [1,2,3,4]
**/
function* genCombinations1(inSet, outSize) {
  if(inSet.length < outSize)
 return;
 
 const out = [];
 for(let i=0; i<outSize; i++)
 out[i] = i;
 // init [0,1,2,3,..,outSize-1]
  
 const maxLast = inSet.length-outSize;
 while(true) {
 {  const yld = [];
  for(let i=0; i<outSize; i++)
 yld[i] = inSet[out[i]];
 yield yld;
 }
 out[outSize-1]++;
 // i= v > i= v
 // (of 0,1,2,3,4,5) out=[0,1,4,6] > out=[0,2,5,6]
 let i;
 for(i=outSize-1; i>0; i--) {
 if(out[i] <= maxLast+i)
 break;
  out[i-1]++;
  }
 if(i===0 && out[i] > maxLast)
 return;
 
 // i= v > i= v
 // (of 0,1,2,3,4,5) out=[0,2,5,6] > out=[0,2,3,4]
 for(i++;i<outSize;i++)
 out[i] = out[i-1]+1;
 }
}