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

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

因此,如果我想要二项式系数x=3,n=4我选择长度等于三的所有字符串.{abc,abd,acd,bcd}.

所以我分两步完成.

是否有更高效的算法,复杂度更低？

链接: 解决方案性能(JSPerf)

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），则到达下一个组合，但如果不是，则必须递增到前一个索引。