combinations with least waste

combinatronicizer.js

 "use strict";
 const _L = require('lodash');
 
 function combinationOfSetsWithLeastWaste(targetSet,candidateGroup){
    /*

    Finds the group of sets whose intersection equals the target set, while
    containing the least waste through extraneous or overlapping items.

    where candidateGroup is a collection of objects as:
    {
    key1 : {name : "stringName", items : [set,of,items]},
    key2 : {...etc}
    }
    and targetSet is an array as:
    [set,of,items]
    */
    
    let WorkingGroup = candidateGroup, 
    WorkingTrgs = targetSet,
    resultGroups =[], 
    testNull = _L(WorkingGroup).reduce((a,b)=>{
        /*the Union of all items on our list intersected with our targets should precisely equal our targets, 
        thus, xor of targets should give us a null set*/
        return _L.union(b.items,a)
    },[])
    .intersection(WorkingTrgs)
    .xor(WorkingTrgs)
    .value(); 


    if (testNull.length >= 1){ //if this isn't a null set, we can't solve.
        throw "Set Group Missing Items: "+testNull.toString();
    }

    while (WorkingTrgs.length >= 1){
        //while we are still hunting for targets, sort to find best match for our remaining targets
        WorkingGroup = sortBestSets(WorkingGroup,WorkingTrgs);
        //adjust our target list to remove items already covered by our best match
        WorkingTrgs = _L(WorkingGroup).head().thru(i=>i.items).xor(WorkingTrgs).value();
        //store the best match
        resultGroups.push(_L.head(WorkingGroup));

    }
    //send off the list of best matches
    return resultGroups.map(i=>i.name);
}


function sortBestSets(SetGroup,targets){
    return _L(SetGroup).map((i)=>{
        //track the intersections of our target set
        i.intr = _L.intersection(i.items, targets); return i; 
    })
    .groupBy(i=>i.intr) //group by distinct intersection of target
    .map((i,k)=>{
     return i.sort((c,d)=>{
        //sort by total length of items
        return c.items.length - d.items.length 
        })
    })
    .map(_L.head) //grab the shortest port of each distinct intersection
    .filter((i)=>{
        return i.items != undefined && i.intr.length != 0; //clear out candidates that don't help us (null intersection is a possible output for the last stage)
    })
    .map((i)=>{
        //format our relevant details to feed into sort
        return {itemSet : i, intr : i.intr, tLen : i.items.length}; 
    })
    .sort((a,b)=>{
        //sort our best candidates by the product of their accuracy and the percentage of the remaining solution they solve
        return  ((a.intr.length / a.tLen) * (a.intr.length / targets.length))  - ((b.intr.length / b.tLen) * (b.intr.length / targets.length)); 
    })
    .map(i=>i.itemSet)     //filter out the baggage data we used for sort and return our list.
    .value();
}