获取对象中所有项目组合的高效算法

Question

给定一个具有n个键的数组或对象，我需要找到长度x的所有组合
给定的X是可变的二项式效率（n，x）。

目前我正在使用这个：

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"]);

输出为：

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

因此，如果我想从< code>n=4中得到二项式系数< code>x=3，我选择所有长度等于3的字符串。{abc，abd，acd，bcd}。

所以我分两步做。

有没有一种复杂度更小、效率更高的算法？

链接： 解决方案性能 （JSPerf）

Answer 1

我们可以创建我们感兴趣的那些组合。此外，我们可以使用指向原始数组的指针，而不是在每次调用中使用切片来克隆数组。这是一个版本。在没有外部全局变量的情况下将其转换为递归是一个练习。

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

Answer 2

您可以使用迭代和递归方法，强调数组的长度和仍然需要的项目。

基本上 combine（） 需要一个数组，其中包含要组合的值和所需组合结果集的大小。

内部函数< code>c()接受一个先前组合的数组和一个起始值作为组合的原始数组的索引。返回的是一个包含所有组合的数组。

第一个调用是allways c([]，0)，因为结果数组为空，起始索引为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; }

Answer 3

你的算法几乎是O（2^n），你可以丢弃很多组合，但元素的数量将是（n！*（n-x）！）/ x！。

要丢弃无用的组合，可以使用索引数组。

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