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

Question

给定一个包含n个键的数组或对象，我需要找到所有长度为x的组合。
给定X是可变的。binomial_coefficient(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"]

如果我想要从n=4中获得二项式系数x=3，那么我会选择所有长度为三的字符串。{abc, abd, acd, bcd}。

因此，我需要分两步进行操作。

是否存在更有效率、复杂度更小的算法？ 链接：Solution performance (JSPerf)

- Panos Kalatzantonakis

---

谢谢大家。我已经创建了一个包含所有答案的jsperf测试链接在此，在不同的浏览器和电脑上测试了几个值之后，我认为David的解决方案是最快的。 - Panos Kalatzantonakis

Answer 1

您的算法几乎是 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));

例如，第一个组合的索引为：[0, 1, 2]，元素为["a", "b", "c"]。为了计算下一个组合，它获取最后一个索引2并尝试递增，如果递增小于最大位置（在本例中为4），则达到下一个组合，但如果不是，则必须递增到以前的索引。

- David Pérez Cabrera

Answer 2

您可以采用迭代和递归的方法，重点在于数组的长度和仍需的项目。
基本上，combine()函数接受一个包含要组合的值的数组以及所需的组合结果集大小。
内部函数c()采用以前制作的组合的数组和原始数组的起始值作为索引进行组合。返回一个包含所有制作的组合的数组。
第一次调用始终是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; }

- Nina Scholz

Answer 3

我们可以只创建我们感兴趣的组合。此外，我们可以使用指向原始数组的指针，而不是在每次调用中使用slice来克隆数组。下面是一个版本。将其转换为递归而不使用外部全局变量留作练习。

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 4

这里是真正的递归。

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

- גלעד ברקן