高效的算法来获取对象中所有项的组合-Java 学习之路

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

所以我分两步完成 .

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

Link: Solution performance (JSPerf)

4 回答

你的算法几乎是 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 ），则到达下一个组合，但如果不是，则必须增加到a以前的指数 .

回复于 2024-05-05T02:25:14+08:00

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

基本上 combine() 采用一个数组，其中包含要组合的值和所需组合结果集的大小 .

内部函数 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; }

回复于 2024-05-05T02:25:14+08:00

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

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

回复于 2024-05-05T02:25:14+08:00

这是真正的递归 .

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

回复于 2024-05-05T02:25:14+08:00

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

4 回答

相关问题