Alle Verteilungen von Elementen zwischen Buckets

Question

Ich stieß vor kurzem auf ein Problem, in dem ich herausfinden muss, wie man Einzelteile in Eimer verteilt, aber ich muss alle Weisen finden, sie zu verteilen.

Die Eingabe kommt als ein Array von Ganzzahlen, die Ihnen sagen, das Maximum, das jede Spalte halten kann, und es muss N Menge von Elementen in dem Array sein.

zum Beispiel:

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 

ich versuchte, dieses Problem in Javascript zu lösen, aber ich bin nicht in der Lage, herauszufinden, wie dieses Problem zu nähern. Ich wollte damit beginnen, die ersten Spalten mit so vielen Zahlen wie möglich zu füllen und mich nach rechts zu bewegen, aber wenn das Maximum-Array größer wird, wird diese Methode ungenauer und ich weiß nicht genau, wie ich sie angehen soll.

Wenn Sie weitere Fragen haben, zögern Sie nicht zu fragen, ob Sie das Problem nicht verstehen.

Der Code, den ich mit in Javascript begann war

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. 
}; 

Ich habe versucht, dieses Problem zu suchen, aber ich habe nie herausgefunden, wie es die Art und Weise zu tun, es wurde hier eingerichtet. Ich habe versucht, ähnliche Probleme zu finden, aber sie hatten immer nichts damit zu tun. Vielleicht suche ich das Problem falsch. Wenn jemand eine hilfreiche Ressource verlinken kann, wäre das großartig.

Wenn Sie irgendwelche Fragen haben, fragen Sie sie bitte. Ich werde auf das Beste meiner Fähigkeiten antworten.

Answer 1

Eine einfache rekursive Lösung mit ECMA 6 Generatoren zu verstehen:

für jede i, legen i Elemente in den ersten Schlitz, wenn sie passen, verteilen dann die anderen unter den übrigen .

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

Sie könnten einen rekursiven Ansatz verwenden, bei dem alle Teile der Bedingungen überprüft werden.

Es funktioniert mit einem Index und einem temporären Array für die Anzahl der Elemente zu halten.

Bei Start ist der Index Null und das Array ist leer. Beim Aufruf von fork wird die erste Exit-Option geprüft, dh die Constraints werden überprüft und bei größerem oder gleichem Zählerstand stoppt die Rekursion.

Die zweite Exit-Option ist, wenn die Summe der Elemente die gewünschte Anzahl erreicht, dann wird das temporäre Array an die Ergebnismenge übergeben und die Rekursion endet.

In allen anderen Fällen wird fork wieder entweder mit genannt

• gleichem Index i und einem inkrementierten Wert der temporären Matrix im Index oder
• inkrementierten Index und die tatsächlichen temporären Matrix.

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

Ein iterativer Ansatz mit einer früheren Überprüfung, ob die Summe zuzüglich Wert kleiner oder gleich ist als die gewünschte Zählung.

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

Hier ist eine gut kommentierte iterative Lösung mit einer interaktiven Demo:

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