高效的算法来获取对象中所有项的组合 [英] Efficient algorithm to get the combinations of all items in object

问题描述

给定一个带有n个键的数组或对象，我需要找到长度 x 的所有组合。

给定 X 是可变的。 binomial_coefficient（n，x）。

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

目前我使用的是：

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 我选择长度等于3的所有字符串。 {abc，abd，acd，bcd}。

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}.

所以我分两步完成。

有吗一个更有效的算法，复杂度更低？

Is there a more efficient algorithm with smaller complexity?

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

推荐答案

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

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例如，第一个组合具有索引： [0,1,2] 和元素 [a，b，c ] 。要计算下一个组合，它得到最后一个索引 2 并尝试增加，如果增量低于最大位置（在这种情况下 4） ），达到下一个组合，但如果不是，则必须增加到之前的索引。

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.

这篇关于高效的算法来获取对象中所有项的组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！