Efficient algorithm to get the combinations of all

问题:

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

Currently I'm using this:

function combine(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 combinations = combine(["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 complexity?

Link: Solution performance (JSPerf)

回答1:

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

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

 function combine(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 combinations = combine(["a", "b", "c", "d"], 3);
    console.log(JSON.stringify(combinations));

For example, the first combination have the indexes: [0, 1, 2] and the elements ["a", "b", "c"]. To compute the next combination, 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 combination is reached, but if It is not, It must increment to a previous index.

回答2:

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

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

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

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

function combine(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(combine(["a", "b", "c", "d"], 3));

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

回答3:

We could create just those combinations 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 combinations = choose(["a", "b", "c", "d"], 3);
console.log(JSON.stringify(combinations));

回答4:

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