find optimal minimum groups and minimum size to divide into preset amount requirements

ideal-bar-length.js

// key is measurement, value is number needed of that measurement
var barLengths = {
    "20": 16, // standard + wide dining window height
    "25.5": 10, // standard windows width
    "37.5": 4, // long dining room windows width
    "21.5": 2, // bathroom window width, again, needs updating because of external framing
    "6": 2, // bathroom window height, probably needs to be increased a bit because we're framing externally
    "31": 2, // door window height, needs verification
};

// function from stack overflow to generate all permutations of an array:
function getSinglePermutation(sourceArray, n) {
    var b = sourceArray.slice();  // copy of the set
    var len = sourceArray.length; // length of the set
    var res;            // return value, undefined
    var i, f;

    // compute f = factorial(len)
    for (f = i = 1; i <= len; i++)
        f *= i;

    // if the permutation number is within range
    if (n >= 0 && n < f) {
        // start with the empty set, loop for len elements
        for (res = []; len > 0; len--) {
            // determine the next element:
            // there are f/len subsets for each possible element,
            f /= len;
            // a simple division gives the leading element index
            i = Math.floor(n / f);
            // alternately: i = (n - n % f) / f;
            res.push(b.splice(i, 1)[0]);
            // reduce n for the remaining subset:
            // compute the remainder of the above division
            n %= f;
            // extract the i-th element from b and push it at the end of res
        }
    }
    // return the permutated set or undefined if n is out of range
    return res;
}
//end SO function

// too big to do them all, so let's do a shuffle instead to get random options. break up the monotony of the opening same.
shuffle = array => {
                      const output = array.slice(0);
                      for (let i = output.length - 1; i > 0; i--) {
                          const j = Math.floor(Math.random() * (i + 1));
                          [output[i], output[j]] = [output[j], output[i]];
                      }
                      return output;
                    };

var bars = [];

for (length in barLengths) {
    for (let i = 0; i < barLengths[length]; i++) {
        bars.push(parseFloat(length))
    }
}

// const allBarOrders = permutator(bars);

var optimalBarOrder = bars;
var optimalLongBarNumber = 10000; // arbitrarily high number to be overwritten immediately
var optimalLongBarLengths = [];
var waste;

var barOptimizationCheck = function(barOrder, longBarLength) {
    let longBars = []
    let currentLongBar = 0;

    // add them together, when they hit the limit, end that bar and start a new one.
    barOrder.forEach(bar => {
        let newLongBar = currentLongBar + bar;
        if (newLongBar > longBarLength) {
            longBars.push(currentLongBar);
            currentLongBar = bar;
        } else {
            currentLongBar = newLongBar;
        }
    })

    // after for loop, push the remainder that never hit longBarLength
    if (currentLongBar > 0) {
        longBars.push(currentLongBar)
    }

    // if fewer longbars, save it;
    // otherwise, if same number and shorter longest bar, save it;
    // otherwise, if both same, then if most leftover distributed margin, save it;
    if (longBars.length < optimalLongBarNumber ||
        
        (longBars.length === optimalLongBarNumber && longBars.reduce((a,b) => a > b ? a:b) < optimalLongBarLengths.reduce((a,b) => a > b ? a:b)) ||
        
        (longBars.length === optimalLongBarNumber &&
         longBars.reduce((a,b) => a > b ? a:b) === optimalLongBarLengths.reduce((a,b) => a > b ? a:b)) &&
         longBars.reduce((a,b) => a + b) < optimalLongBarLengths.reduce((a,b) => a > a + b)
         )
        {
        optimalBarOrder = barOrder;
        optimalLongBarNumber = longBars.length;
        optimalLongBarLengths = longBars;
        waste = (longBarLength * optimalLongBarNumber) - optimalLongBarLengths.reduce((a,b) => a+b);
    }
}

// var checkThisMany = 100000;
var checkThisMany = 100000000;
var start = 1;

var maxLongBarLength = 38; // pre-set number to determine (max) how long you want the bars you're looking to optimize...
var barDict = {};

//37
for (let longBarLength = 144; longBarLength <= maxLongBarLength; longBarLength++) {
    
    for (let i = start; i < start + checkThisMany; i++) {
         // barOptimizationCheck(getSinglePermutation(bars, i))
         barOptimizationCheck(shuffle(bars), longBarLength)
    }

    barDict[longBarLength] = {
        optimalBarOrder,
        optimalLongBarLengths,
        howMany: optimalLongBarNumber,
        minMargin: longBarLength - optimalLongBarLengths.reduce((a,b) => a > b ? a : b),
        waste,
        wastePercent: Math.floor((waste / (longBarLength * optimalLongBarNumber)) * 100) + "%",
    };

    // clear these values
    optimalBarOrder = bars;
    optimalLongBarNumber = 10000; // arbitrarily high number to be overwritten immediately
    optimalLongBarLengths = [];
    waste = 0;
}
    

console.log(barDict)

{ '47':
{ optimalBarOrder:
[ 37.5,
37.5,
6,
25.5,
20,
20,
20,
37.5,
6,
20,
20,
25.5,
20,
37.5,
20,
25.5,
25.5,
20,
31,
20,
25.5,
21.5,
20,
20,
25.5,
21.5,
20,
25.5,
20,
20,
25.5,
31,
25.5,
20,
25.5,
20 ],
optimalLongBarLengths:
[ 37.5,
43.5,
45.5,
40,
43.5,
40,
45.5,
37.5,
45.5,
45.5,
31,
45.5,
41.5,
45.5,
41.5,
45.5,
45.5,
31,
45.5,
45.5 ],
howMany: 20,
minMargin: 1.5,
waste: 98,
wastePercent: '10%' } }
this tells me what order I need to make the cuts in, how much of the length of each bar I'll use, how many of these bars I need, how much margin I'll have on the longest bars, how many inches will be wasted, and what percent of the whole I purchased will go to waste (end pieces that are too short).