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

本文介绍了高效的算法来获取对象中所有项的组合的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

给定一个带有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.