桶之间的所有项目分布

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>