Given an array or object with n keys, I need to find all binations with length x.
Given X is variable. binomial_coefficient(n,x).

Currently I'm using this:

function bine(items) {
    var result = [];
    var f = function(prefix, items) {
        for (var i = 0; i < items.length; i++) {
            result.push(prefix + items[i]);
            f(prefix + items[i], items.slice(i + 1));
        }
    }
    f('', items);
    return result;
}

var binations = bine(["a", "b", "c", "d"]);

The output is:

["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"]

So if I want the binomial coefficient x=3 from n=4 I select all the strings with length equal to three. {abc, abd, acd, bcd}.

So I do this in two steps.

Is there a more efficient algorithm with smaller plexity?

Link: Solution performance (JSPerf)

Given an array or object with n keys, I need to find all binations with length x.
Given X is variable. binomial_coefficient(n,x).

Currently I'm using this:

function bine(items) {
    var result = [];
    var f = function(prefix, items) {
        for (var i = 0; i < items.length; i++) {
            result.push(prefix + items[i]);
            f(prefix + items[i], items.slice(i + 1));
        }
    }
    f('', items);
    return result;
}

var binations = bine(["a", "b", "c", "d"]);

The output is:

["a", "ab", "abc", "abcd", "abd", "ac", "acd", "ad", "b", "bc", "bcd", "bd", "c", "cd", "d"]

So if I want the binomial coefficient x=3 from n=4 I select all the strings with length equal to three. {abc, abd, acd, bcd}.

So I do this in two steps.

Is there a more efficient algorithm with smaller plexity?

Link: Solution performance (JSPerf)

• javascript
• algorithm
• dynamic-programming
• memoization
• binomial-coefficients

• Thank you all. I've created a jsperf test with all the answers here, after testing several values in different browsers and PCs I think David has the fastest solution – Panos Kalatzantonakis Commented Jul 28, 2017 at 7:27

4 Answers 4

Your algorithm is almost O(2^n), you can discard a lot of binations, but the num of elements will be (n! * (n-x)!) / x!.

To discard the useless binations you can use an indexed array.

 function bine(items, numSubItems) {
        var result = [];
        var indexes = new Array(numSubItems);
        for (var i = 0 ; i < numSubItems; i++) {
            indexes[i] = i;
        }
        while (indexes[0] < (items.length - numSubItems + 1)) {
            var v = [];
            for (var i = 0 ; i < numSubItems; i++) {
                v.push(items[indexes[i]]);
            }
            result.push(v);
            indexes[numSubItems - 1]++;
            var l = numSubItems - 1; // reference always is the last position at beginning
            while ( (indexes[numSubItems - 1] >= items.length) && (indexes[0] < items.length - numSubItems + 1)) {
                l--; // the last position is reached
                indexes[l]++;
                for (var i = l +1 ; i < numSubItems; i++) {
                    indexes[i] = indexes[l] + (i - l);
                }
            }        
        }
        return result;
    }

    var binations = bine(["a", "b", "c", "d"], 3);
    console.log(JSON.stringify(binations));

For example, the first bination have the indexes: [0, 1, 2] and the elements ["a", "b", "c"]. To pute the next bination, It get the last index 2 and try to increment, if the increment is lower than the max position (in this case 4), the next bination is reached, but if It is not, It must increment to a previous index.

You could use an iterative and recursive approach with stress on the length of the array and the still needed items.

Basically bine() takes an array with the values to bine and a size of the wanted bination results sets.

The inner function c() takes an array of previously made binations and a start value as index of the original array for bination. The return is an array with all made binations.

The first call is allways c([], 0), because of an empty result array and a start index of 0.

function bine(array, size) {

    function c(part, start) {
        var result = [], i, l, p;
        for (i = start, l = array.length; i < l; i++) {
            p = part.slice(0);                       // get a copy of part
            p.push(array[i]);                        // add the iterated element to p
            if (p.length < size) {                   // test if recursion can go on
                result = result.concat(c(p, i + 1)); // call c again & concat rresult
            } else {
                result.push(p);                      // push p to result, stop recursion
            }
        }
        return result;
    }

    return c([], 0);
}

console.log(bine(["a", "b", "c", "d"], 3));

.as-console-wrapper { max-height: 100% !important; top: 0; }

We could create just those binations we are interested in. Also, rather than cloning arrays by using slice in each call, we can use a pointer to the original array. Here's one version. Converting it to recursion without an external global variable is left as an exercise.

function choose(ns,r){
  var res = [];

  function _choose(i,_res){
    if (_res.length == r){
      res.push(_res);
      return;

    } else if (_res.length + ns.length - i == r){
      _res = _res.concat(ns.slice(i));
      res.push(_res);
      return
    }

    var temp = _res.slice();
    temp.push(ns[i]);

    _choose(i + 1,temp);
    _choose(i + 1,_res);
  }

  _choose(0,[]);
  return res;
}

var binations = choose(["a", "b", "c", "d"], 3);
console.log(JSON.stringify(binations));

And here's the true recursion.

function seq(a,b){
  var res = [];
  for (var i=a; i<=b; i++)
    res.push(i);
  return res;
}

function f(n,k){
  if (k === 0)
    return [[]];
    
  if (n === k)
    return [seq(1,n)];
    
  let left = f(n - 1, k - 1),
      right = f(n - 1, k);
    
  for (let i=0; i<left.length; i++)
    left[i].push(n);
  
  return left.concat(right);
}

console.log(JSON.stringify(f(4,3)))