create a loop for (N choose X)

Question

Say I have a list of N members:

const list = [0, 1, 2, ...(N-1)];

I want to do (N choose X), mathematically, so I need to create a function:

const findAllCombinations = (x, list) => {
     // return all x combinations of the list
};

if X were 2, I could do this:

const findAllCombinations = (x, list) => {
    for(let i = 0; i < list.length; i++){
      for(let j = i+1; j < list.length; j++){
           // N choose 2
       }
     }
};

but not certain off-hand how to loop in a way to capture N choose X, it would be nice to do this iteratively instead of recursively if possible! But a recursive solution would be just fine.

Here is my attempt, but it's wrong:

 const combine = (x, list) => {
    
    // Note: N = list.length

    if(list.length < x){
        throw new Error('not enough elements to combine.');
    }

    if (x < 1) {
        return [];
    }

    const ret = [];

    for(let v of combine(x-1, list.slice(1))){
        ret.push([list[0], ...v]);
    }

    return ret;
}
    

console.log(
   combine(3, ['a','b,'c','d'])
)

the goal would be to get these 4 combinations:

[a,b,c]
[a,b,d]
[a,c,d]
[b,c,d]

..because (4 choose 3) = 4.

Here is my desired output:

combine(0,[1,2,3]) => [[]] // as  N choose 0 = 1
combine(1,[1,2,3]) => [[1],[2],[3]] // as  N choose 1 = N
combine(2,[1,2,3]) => [[1,2],[1,3],[2,3]]]] // as  N choose N-1 = N
combine(3,[1,2,3]) => [[1,2,3]] // as  N choose N = 1

to see a better list of desired output, see: https://gist.github.com/ORESoftware/941eabac77cd268c826d9e17ae4886fa

Answer 1

Here is a recursive approach I got from modifying your code:

const combine = (x, list) => {
  if (x < 1) return [[]];

  let N = list.length;
  if (N < x) return [];
 
  const ret = [];
  for (let i = 0; i <= N - x; i++) {
    for (let v of combine(x - 1, list.slice(i + 1))) {
      ret.push([list[i], ...v]);
    }
  }
  return ret;
}

console.log(JSON.stringify(combine(0, [1, 2, 3])));
console.log(JSON.stringify(combine(1, [1, 2, 3])));
console.log(JSON.stringify(combine(2, [1, 2, 3])));
console.log(JSON.stringify(combine(3, [1, 2, 3])));

console.log(JSON.stringify(combine(0, [1, 2, 3, 4])));
console.log(JSON.stringify(combine(1, [1, 2, 3, 4])));
console.log(JSON.stringify(combine(2, [1, 2, 3, 4])));
console.log(JSON.stringify(combine(3, [1, 2, 3, 4])));
console.log(JSON.stringify(combine(4, [1, 2, 3, 4])));

I originally wrote a base case for choosing 1 element (if (x === 1) return list.map(e => [e]);), but it turns out that it isn't actually necessary, my base case for "x<1" works just fine.

The i <= N - x part was not that obvious to come up with, but you could replace it with i < N (easier to understand but less efficient). It still works since there is no error thrown; when there are not enough elements, the recursion will just give you [], so "let v of ..." won't really do anything.

But if you changed the "not enough elements" case to if (N < x) throw new Error("not enough elements");, then it works fine with i <= N-x but throws an error if you used i < N.