有效的算法來獲得對象中所有項目的組合

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)

Answer 1

你的算法是幾乎O(2^n)，則可以放棄很多的組合，但元素的NUM將(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），則達到下一個組合，但如果不是，則它必須增加到以前的指數。

Answer 2

我們可以創建不僅僅是那些我們感興趣的組合也，而不是在每次調用使用切片克隆陣列，我們可以用一個指向原始數組。這是一個版本。將其轉換爲不帶外部全局變量的遞歸是一個練習。

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 3

您可以使用迭代和遞歸方法來處理數組長度和仍然需要的項目。

基本上combine()需要一個數組來組合值和所需組合結果集的大小。

內部函數c()需要先前創建的組合的數組，並將起始值作爲用於組合的原始數組的索引。返回是一個包含所有組合的數組。

由於空結果數組和起始索引爲0，所以第一次調用是全程c([], 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; }

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