2016-03-01 57 views
1

我想找到一種方法,將數組中的所有可能性組合到四個百分比之間。找到4個百分點之間的所有可能性

結果想:

possibilities = [[100,0,0,0],[99,1,0,0],[99,0,1,0],...,[0,0,1,99],[0,0,0,100]] 

我使用這個功能,但它很慢,似乎並沒有產生所有的可能性。

combinePossibilities : function(a, min, max) { 
    var deferred = $q.defer(); 
    function toObject(arr) { 
     var rv = {}; 
     for (var i = 0; i < arr.length; ++i){ 
      rv['fund'+i] = arr[i]; 
     } 
     return rv; 
    } 
    var fn = function(n, src, got, all) { 
     if (n === 0) { 
      if (got.length > 0) { 
       var total = 0; 
       angular.forEach(got, function(value){ 
        total += value; //GET TOTAL OF THE COMBINATION 
       }); 
       if(total === 100){ 
        all.push(toObject(got)); 
       } 
      } 
      return; 
     } 
     for (var j = 0; j < src.length; j++) { 
      fn(n - 1, src.slice(j + 1), got.concat([src[j]]), all); 
     } 
     return; 
    }; 
    var all = []; 
    for (var i = min; i <= max; i++) { 
     console.log(a); 
     fn(i, a, [], all); 
    } 
    deferred.resolve(all); 
    return deferred.promise; 
} 

我在這裏Find all possible subset combos in an array?發現了這個功能,並修改它只需要在我的數組結果等於100%。

任何線索?

謝謝。

+1

你說的所有的可能性呢?像[[0,0,0,0]]到[0,0,0,0]]到[[0,0,1,0]]最終到達[100,100,100,100]? – Ivar

+0

更清楚地定義你的問題。什麼是輸入和什麼是預期的輸出? –

+0

@MattBurland,我想要一個數組的數組,它的所有可能性等於100. results = [[100,0,0,0],[99,1,0,0],...,[95,2 ,1,2],...,[25,25,25,25] ...,[0,0,0,100]。希望我很清楚。 –

回答

2

這個建議是一個函數遞歸函數,它需要和和長度。它返回一個數組,其中包含從總和到零的組合值的數組。

function combine(sum, length, part) { 
    var result = [], 
     i = sum; 

    part = part || []; 
    if (length === 1) { 
     return [part.concat(sum)]; 
    } 
    if (length === 0) { 
     return [part]; 
    } 
    do { 
     result = result.concat(combine(sum - i, length - 1, part.concat(i))); 
    } while (i--); 
    return result; 
} 

工作原理:

它首先給定sumlength和一個空result集,以及一個迭代變量isum值。如果沒有給出part,則分配空數組。

現在遵循的(剩下的)一些檢查length和他們的特殊待遇,如果是

  • 1:這是最後一次迭代和sum只剩下。然後將由sum連接的部分結果part返回到數組中。

  • 0:沒有更多的迭代,然後返回數組中的部分結果part

如果length既不1也不0,然後interate在sum爲零。

combine的呼叫需要減小sum,遞減length和部分結果parti值。

combine()的調用結果連接到result集合。

示例combine(5, 3)

length: 21 
[ 
    [5, 0, 0], 
    [4, 1, 0], 
    [4, 0, 1], 
    [3, 2, 0], 
    [3, 1, 1], 
    [3, 0, 2], 
    [2, 3, 0], 
    [2, 2, 1], 
    [2, 1, 2], 
    [2, 0, 3], 
    [1, 4, 0], 
    [1, 3, 1], 
    [1, 2, 2], 
    [1, 1, 3], 
    [1, 0, 4], 
    [0, 5, 0], 
    [0, 4, 1], 
    [0, 3, 2], 
    [0, 2, 3], 
    [0, 1, 4], 
    [0, 0, 5] 
] 

兩個例子工作代碼:

  • combine(5, 3)
  • combine(10, 4)

function combine(sum, length, part) { 
 
    var result = [], 
 
     i = sum; 
 

 
    part = part || []; 
 
    if (length === 1) { 
 
     return [part.concat(sum)]; 
 

 
    } 
 
    if (length === 0) { 
 
     return [part]; 
 
    } 
 
    do { 
 
     result = result.concat(combine(sum - i, length - 1, part.concat(i))); 
 
    } while (i--); 
 
    return result; 
 
} 
 

 
function print(array) { 
 
    document.write('<pre>length: ' + array.length + '\n' + JSON.stringify(array, 0, 4) + '</pre>'); 
 
} 
 

 
print(combine(5, 3)); 
 
print(combine(10, 4));

+1

這正是我所需要的。非常感謝@NinaScholz! 176850可能性,這是相當多的。 –

+1

解釋清楚。 THKS。 –

相關問題