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).

Answer 2

Here is a more readable rewrite of @EricLavault's code, using the same iterative algorithm.

//Creates an iterator over (n C k)
function* findAllCombinations(k, arr) {
  const n = arr.length

  if (k > n)
    return
  
  //Array of indices of elements of `arr`; this is our current combination
  const iArr = Array.from({length: k}, (_, i) => i)
  
  function next() {
    //Find the last index that has room to advance without resetting
    const toAdvance = iArr.findLastIndex((i, j) => n-i > k-j)
    //                                             ^^^   ^^^
    //                                             |||   +++--- Number of elements that have to be chosen 
    //                                             +++--------- Number of elements that we can choose from
    
    //If there's no such index, we've reached the last combination
    if(toAdvance === -1)
      return false

    //Advance the index
    iArr[toAdvance]++

    //Reset all indices after the advanced one to (previous + 1)
    for(let i = toAdvance + 1; i < k; i++)
      iArr[i] = iArr[i-1] + 1

    return true
  }
  
  do 
    //Map indices to real values from the array
    yield iArr.map(e => arr[e])
  while(next())
}

for(const v of findAllCombinations(2, ['a', 'b', 'c', 'd', 'e'])) 
  console.log(v)

The .findLastIndex() method is a very recent addition to the language, so it may not be supported by all platforms.

It's possible to do without that, but I think it's cleaner to just implement findLastIndex separately and use that.

function findLastIndex(arr, predicate) {
  for(let i = arr.length - 1; i >= 0; i--) {
    if(predicate(arr[i], i, arr)) {
      return i
    }
  }
  return -1
}

//Creates an iterator over (n C k)
function* findAllCombinations(k, arr) {
  const n = arr.length

  if (k > n) {
    return
  }
  
  //Array of indices of elements of `arr`; this is our current combination
  const iArr = Array.from({length: k}, (_, i) => i)
  
  function next() {
    //Find the last index that has room to advance without resetting
    const toAdvance = findLastIndex(iArr, (i, j) => n-i > k-j)
    //                                              ^^^   ^^^
    //                                              |||   +++--- Number of elements that have to be chosen 
    //                                              +++--------- Number of elements that we can choose from
    
    //If there's no such index, we've reached the last combination
    if(toAdvance === -1) {
      return false
    }

    //Advance the index
    iArr[toAdvance]++

    //Reset all indices after the advanced one to (previous + 1)
    for(let i = toAdvance + 1; i < k; i++) {
      iArr[i] = iArr[i-1] + 1
    }

    return true
  }
  
  do {
    //Map indices to real values from the array
    yield iArr.map(e => arr[e])
  } while(next())
}

for(const v of findAllCombinations(2, ['a', 'b', 'c', 'd', 'e'])) {
  console.log(v)
}

Answer 3

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.

Answer 4

It turned out we can avoid using recursions.

I thought of itertools.combinations in Python.
CPython is open source so we can see the source code in C. https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c
You can see the function definitions for itertools_combinations_impl and combinations_next.

There are those refCount and garbage collector stuff, though, which may not be relevant to another language.

I attempted to write a version of "combinationsobject" in TypeScript and added some tests after that ( TS playground ), then it's easy to get JS from the compilation output:

"use strict";
//this class is based on https://github.com/python/cpython/blob/main/Modules/itertoolsmodule.c
class CombinationObject {
    constructor(list, r) {
        let n = list.length;
        this.pool = list;
        this.indices = [];
        for (let i = 0; i < r; i++)
            this.indices[i] = i;
        this.result = null;
        this.r = r;
        this.stopped = r > n;
    }
    next() {
        if (this.stopped)
            return null;
        let { pool, indices, r } = this;
        if (this.result === null) {
            //first pass 
            this.result = [];
            for (let i = 0; i < r; i++) {
                let index = indices[i];
                this.result[i] = pool[index];
            }
        }
        else {
            this.result = this.result.slice();
            let n = pool.length;
            let i; //needs to be used outside the for loop 
            /* Scan indices right-to-left until finding one that is not at its maximum (i + n - r). */
            for (i = r - 1; i >= 0 && indices[i] == i + n - r; i--) { }
            if (i < 0) {
                this.stopped = true;
                return null;
            }
            /* Increment the current index which we know is not at its maximum.
              Then move back to the right setting each index to its lowest possible value (one higher than the index to its left).
            */
            indices[i]++;
            for (let j = i + 1; j < r; j++) {
                indices[j] = indices[j - 1] + 1;
            }
            /* Update the result for the new indices starting with i, the leftmost index that changed */
            for (; i < r; i++) {
                let index = indices[i];
                this.result[i] = pool[index];
            }
        }
        return this.result;
    }
}
let list = ["One", 2, "Three", 4, 5, 'Six'];
let K = 3;
const LIMIT = 1000;
let co = new CombinationObject(list, K);
let count = 0;
while (!co.stopped && count < LIMIT) {
    let result = co.next();
    if (result === null)
        break;
    console.log(result);
    count++;
}
function factorial(n) {
    let t = 1;
    for (let i = 2; i <= n; i++)
        t *= i;
    return t;
}
function nCk(n, k) {
    if (k > n)
        return 0;
    return factorial(n) / factorial(n - k) / factorial(k);
}
console.log(nCk(list.length, K));
console.log(count);