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 an iterative approach that uses combinations of indexes from the given set.

Starting from an initial combination of k indexes, those are shifted/incremented in-place in order to obtain the next combination of length k, and so on :

function * combinations(set, k) {
  const n = set.length;
  if (k > n)
    return;

  // Shift combi indexes to make it the next k-combination. Return true if
  // successful, false otherwise (when there is no next of that length).
  const next = (combi, i) => {
    if (++combi[i] < n)
      return true;
    let limit = n;
    while (i > 0) {
      if (++combi[--i] < --limit) {
        let idx = combi[i];
        while (++i < combi.length)
          combi[i] = ++idx;
        return true;
      }
    }
    return false;
  };

  const combi = Array.from(Array(k), (_, i) => i);
  const i = k-1;

  do yield combi.map(j => set[j]);
  while (next(combi, i));
}

This is much more efficient that one might think, especially when compared to a recursive algorithm that always start from the the empty combination regardless of k (the function next() could probably be optimized though).

A more sophisticated version, which allows to specify a list of values for k and whether or not to allow repetitions, can be found here (and just above it the recursive implementation).