桶之間的所有項目分佈

Question

我最近遇到了一個問題，我需要弄清楚如何將項目分發到桶中，但我需要找到所有分配方法。

輸入以整數數組的形式出現，它告訴您每列可以容納的最大值，並且數組中必須有N個項目。

例如：

maxItems = 3 
maximums = [4,2,1] # The order of maximums DOES matter meaning 
# This means that the results of maximums = [2,4,1] are different from maximums = [1,2,4] 
outputs = [[3,0,0],[2,1,0],[1,1,1],[2,0,1],[0,2,1]] # results are in no particular order 
# notice how the sum of each result is equal to maxItems and each value in each of the rows are less than the value inside of maximums 

我試圖解決在JavaScript這個問題，但我無法弄清楚如何解決這個問題。我想首先填寫儘可能多的數字並開始向右移動，但隨着最大值數組變大，此方法變得更加不準確，我完全不知道如何處理它。

如果您還有其他問題，請隨時詢問您是否不瞭解問題。

我開始了與該代碼在JavaScript是

var all_combinations = function(N, maximums){ 
    var empty = maximums.map(function(){return 0;}); // create empty array size of maximums filled with 0s 
    var s = 0; 
    for (var i = 0; i < empty.length && s < N;){ 
     if (empty[i] >= maximums[i]){i++;continue;} 
     empty[i]++; 
     s++; 
    } // fill the left side with as many items as possible 

    // Then i would proceed to move one item at a time to the right side but some how i would need to do it for the whole array and this is where I get stuck. 
}; 

我試着搜索了這個問題，但我從來沒有發現如何做到這一點它是在這裏設立的方式。我試着找到類似的問題，但他們總是與此無關。也許我正在尋找錯誤的問題。如果有人可以鏈接一個很有用的資源。

如果您有任何問題，請詢問他們。我會盡我所能回答。

Answer 1

一個易於理解與ECMA 6臺發電機遞歸解決方案：

每個i，將i物品進入第一插槽它們是否適合，那麼剩下之間分配等。

function* bucket_distributions(capacities,nItems){ 
 
    if (capacities.length==1) { 
 
     if (capacities[0] >= nItems) 
 
     yield [nItems]; 
 
    } 
 
    else if (capacities.length>1) { 
 
     for (var i=Math.min(capacities[0],nItems);i>=0;i--) { 
 
     for (subdist of 
 
      bucket_distributions(capacities.slice(1),nItems-i)) 
 
      yield [i].concat(subdist); 
 
     } 
 
    } 
 
} 
 

 
console.log(Array.from(bucket_distributions([4,2,1],3)))

Answer 2

您可以使用遞歸方法檢查約束的所有部分。

它與一個索引和一個臨時數組一起工作，以保持項目的數量。

開始時，索引爲零，數組爲空。通過調用fork，檢查第一個退出選項，這意味着檢查約束條件，如果計數較大或相等，則遞歸停止。

第二個退出選項是當項目總數達到所需計數時，臨時數組被推送到結果集並遞歸結束。

在所有其他情況下，fork與任一

• 相同的索引i和臨時數組的索引處的遞增值，或
• 遞增的索引和實際臨時數組再次調用。

function getCombination(max, count) { 
 

 
    function fork(index, temp) { 
 
     var sum = temp.reduce((a, b) => a + b, 0); 
 
     if (max.some((a, i) => (temp[i] || 0) > a) || index === max.length || sum > count) { 
 
      return; 
 
     } 
 
     if (sum === count) { 
 
      result.push(temp); 
 
      return; 
 
     } 
 
     fork(index, max.map((a, i) => (temp[i] || 0) + (i === index))); 
 
     fork(index + 1, temp); 
 
    } 
 

 
    var result = []; 
 
    fork(0, []); 
 
    return result; 
 
} 
 

 
console.log(getCombination([4, 2, 1], 3));

.as-console-wrapper { max-height: 100% !important; top: 0; }

與以前的檢查，如果總和加上值比所需數量小於或等於一個迭代的方法。

function getCombination(max, count) { 
 

 
    function iter(index, sum, temp) { 
 
     var i; 
 
     if (count === sum) { 
 
      result.push(temp); 
 
      return; 
 
     } 
 
     for (i = max[index]; i >= 0; i--) { 
 
      if (sum + i <= count) { 
 
       iter(index + 1, sum + i, temp.concat(i)); 
 
      } 
 
     } 
 
    } 
 

 
    var result = []; 
 
    iter(0, 0, []); 
 
    return result; 
 
} 
 

 
console.log(getCombination([4, 2, 1], 3));

.as-console-wrapper { max-height: 100% !important; top: 0; }

Answer 3

下面是一個交互式演示一個良好註釋迭代求解：

// reducer function for calculating sum of array 
 
function sum(prev, next) { 
 
    return prev + next; 
 
} 
 

 
// returns the contextual constraints of a bucket 
 
function bucketMinMax(maxItems, otherItems, bucketMax) { 
 
    return { 
 
    // minimum values in bucket to meet maxItems 
 
    min: Math.max(0, maxItems - otherItems), 
 
    // maximum values in bucket to meet maxItems 
 
    max: Math.min(maxItems, bucketMax), 
 
    }; 
 
} 
 

 
// takes an incomplete combination and expands it with the next bucket 
 
// starting from the left 
 
function expandCombination(maxItems, maximums, combinations) { 
 
    // get next combo group to expand 
 
    var comboGroup = combinations.shift(); 
 
    // get index of expansion bucket 
 
    var index = comboGroup.length; 
 
    // calculate maximum possible otherItems 
 
    var otherItems = maximums.slice(index + 1).reduce(sum, 0); 
 

 
    // removes already used spaces from maxItems in combination group being expanded 
 
    maxItems -= comboGroup.reduce(sum, 0); 
 

 
    // get constraints for expansion bucket 
 
    var {min, max} = bucketMinMax(maxItems, otherItems, maximums[index]); 
 

 
    for (var i = min; i <= max; i++) { 
 
    // add combo group expansions to output 
 
    combinations.push(comboGroup.concat([i])); 
 
    } 
 
} 
 

 
// main function 
 
function allCombinations(maxItems, maximums) { 
 
    // will eventually contain all combinations 
 
    var output = [[]]; 
 

 
    // loops through array of combinations, expanding each one iteratively 
 
    while (output.length > 0 && output[0].length < maximums.length) { 
 
    // takes incomplete combination group and expands it with possible values 
 
    // for next bucket starting from the left 
 
    expandCombination(maxItems, maximums, output); 
 
    } 
 

 
    return output; 
 
} 
 

 
document.addEventListener('change',() => { 
 
    var maxes = JSON.parse(maximums.value); 
 
    var items = JSON.parse(maxItems.value); 
 
    
 
    console.log(JSON.stringify(allCombinations(items, maxes))); 
 
}); 
 

 
document.dispatchEvent(new Event('change'));

<label>maxItems 
 
<input id="maxItems" value="3"> 
 
</label> 
 
<label>maximums 
 
<input id="maximums" value="[4,2,1]"> 
 
</label>