Need help in getting as much unique beer as possible

Question

Let's say I have a bar and cars stop by to pick up beer(s) before heading to the beach. Each car has a trunk size (remainingSum) and each beer has a size (beer.size)

I would like to provide customers with the beer combination choices (AllCombinations) that their car trunk can fit, but unique combinations.

For example, Input:

let Beers = [ 
    {id: 1, size: 4},
    {id: 5, size: 1},
    {id: 10, size: 0.5},
    {id: 11, size: 1},
    {id: 12, size: 2},
    {id: 13, size: 1},
];

let TrunkSize = 2;

Expected Output

AllCombinations = [ // no duplicates
    [{id: 5, size: 1}, {id: 10, size: 0.5}],
    [{id: 5, size: 1}, {id: 11, size: 1}],
    [{id: 5, size: 1}, {id: 13, size: 1}],
    [{id: 10, size: 0.5}, {id: 11, size: 1}],
    [{id: 10, size: 0.5}, {id: 13, size: 1}],
    [{id: 11, size: 1}, {id: 13, size: 1}],
    [{id: 5, size: 1}],
    [{id: 11, size: 1}],
    [{id: 12, size: 2}],
    [{id: 13, size: 1}],
    [{id: 10, size: 0.5}],
]

Current Output

AllCombinations = [ 
    [{id: 5, size: 1}, {id: 10, size: 0.5}],  // dup a
    [{id: 5, size: 1}, {id: 11, size: 1}],    // dup c
    [{id: 5, size: 1}, {id: 13, size: 1}],    // dup d
    [{id: 10, size: 0.5}, {id: 5, size: 1}],  // dup a
    [{id: 10, size: 0.5}, {id: 11, size: 1}], // dup b
    [{id: 10, size: 0.5}, {id: 13, size: 1}], // dup e
    [{id: 11, size: 1}, {id: 13, size: 1}],   // dup f
    [{id: 11, size: 1}, {id: 10, size: 0.5}], // dup b
    [{id: 11, size: 1}, {id: 5, size: 1}],    // dup c
    [{id: 13, size: 1}, {id: 5, size: 1}],    // dup d
    [{id: 13, size: 1}, {id: 10, size: 0.5}], // dup e
    [{id: 13, size: 1}, {id: 11, size: 1}],   // dup f
    [{id: 5, size: 1}],
    [{id: 11, size: 1}],
    [{id: 12, size: 2}],
    [{id: 13, size: 1}],
    [{id: 10, size: 0.5}]
]

Current function:

AllCombinations = [];
GetCombinations(currentCombination, beers, remainingSum) 
{ 

    if (remainingSum < 0) 
        return;// Sum is too large; terminate recursion

    else {
        if (currentCombination.length > 0) 
        {
            currentCombination.sort();  
            var uniquePermutation = true;

            for (var i = 0; i < this.AllCombinations.length; i++) 
            {
                if (currentCombination.length == this.AllCombinations[i].length) 
                {
                    for (var j = 0; currentCombination[j] == this.AllCombinations[i][j] && j < this.AllCombinations[i].length; j++);  // Pass

                    if (j == currentCombination.length) {
                        uniquePermutation = false; 
                        break;
                    }
                }
            }

            if (uniquePermutation)
                this.AllCombinations.push(currentCombination);
        }
    }

    for (var i = 0; i < beers.length; i++) {
        var newChoices = beers.slice();       
        var newCombination = currentCombination.concat(newChoices.splice(i, 1)); 
        var newRemainingSum = remainingSum - beers[i].size;
        this.GetCombinations(newCombination, newChoices, newRemainingSum);
    }
}

Shouldn't `Beers` be an array, that holds objects instead of an object that has no property names, but only objects? — Scott Marcus, May 18 '17 at 20:25
@ScottMarcus I think the question text just may have typos for `Beers` and `AllCombinations`. Should be `[ {}, {}, ...]` rather than `{ {}, {}, ...}` — mhodges, May 18 '17 at 20:33
If beers is an array it should be surrounded by brackets not braces. — James, May 18 '17 at 20:33
@KyleKhalaf No, `Beers` is currently an `object` that contains other `object`s. if it was an `array` (which it should be), it should be surrounded with `[` and `]`, not `{` and `}`. — Scott Marcus, May 18 '17 at 20:34
@ScottMarcus `{ {}, {}, ...}` is a syntax error, so I think it was safe to presume it was a typo. OP has confirmed. — mhodges, May 18 '17 at 20:46
@KyleKhalaf I fixed your question for you - but just so you know, in JavaScript, `[]` denotes an array and `{}` denotes an object - the two are not interchangeable. — mhodges, May 18 '17 at 20:53
@mhodges I know, it was just a typo cz I typed them really quick. I need to revert your edit, since the function returns combinations of **objects** but their sizes values — Khalil Khalaf, May 18 '17 at 20:55

score 1 · Answer 1 · answered May 18 '17 at 21:08

Here's another approach:

let Beers = [ 
            {id: 1, size: 4},
            {id: 5, size: 1},
            {id: 10, size: 0.5},
            {id: 11, size: 1},
            {id: 12, size: 2},
            {id: 13, size: 1},
];

let TrunkSize = 2;

// get all combinations (stolen from http://stackoverflow.com/questions/5752002/find-all-possible-subset-combos-in-an-array )
function combinations(array) {
    return new Array(1 << array.length).fill().map(
        (e1,i) => array.filter((e2, j) => i & 1 << j));
}

// filter them out if the summed sizes are > trunksize
var valids = combinations(Beers).filter(function(el) {
  return el.reduce(function(a,b){return a+b.size;}, 0) <= TrunkSize;
});

console.log(valids);

Danziger · Answer 2 · 2017-05-18T21:28:49.743

To get all possible combinations without duplicates, you can represent your combinations with a set of N bits, where N = # of .

So you should get a table that looks like this:

The 1 tell you which beers are part of that possible combination. Then you just sum their sizes. If you get a sum greater than trunkCapacity, abort that loop.

After the loop, check that the total size of that combination is within the limits and add it to the list of combinations.

function getCombination(beers, trunkSize) {
  const beersCount = beers.length;
  const combinationsCount = Math.pow(2, beersCount);
  
  const combinations = [];
  
  let i = 0; // Change this to 1 to remove the empty combination that will always be there.
  
  while(i < combinationsCount) {
    const binary = i.toString(2);
    const bits = Array.prototype.concat.apply(Array(beersCount - binary.length).fill(0), binary.split('').map(parseInt));
    
    const combination = [];
    
    let bit = 0;
    let total = 0;
    
    while(bit < beersCount && total <= trunkSize) {
      if (bits[bit]) {
        const beer = beers[bit];

        total += beer.size;
      
        combination.push(beer);
      }
      
      ++bit;
    }
    
    if (total <= trunkSize) {
      combinations.push(combination)
    }
  
    ++i;
  }
  
  return combinations;
}

const combinations = getCombination([ 
  {id: 1, size: 4},
  {id: 5, size: 1},
  {id: 10, size: 0.5},
  {id: 11, size: 1},
  {id: 12, size: 2},
  {id: 13, size: 1},
], 2);

console.log(JSON.stringify(combinations, null, 2));

score 1 · Accepted Answer · answered May 18 '17 at 21:13

I've edited your code, fixing sort & checking with additional array & stringify:

let Beers = [ 
    {id: 1, size: 4},
    {id: 5, size: 1},
    {id: 10, size: 0.5},
    {id: 11, size: 1},
    {id: 12, size: 2},
    {id: 13, size: 1},
];

let TrunkSize = 2;

AllCombinations = [];
var combStrings = []
function GetCombinations(currentCombination, beers, remainingSum) 
{ 

    if (remainingSum < 0) 
        return;// Sum is too large; terminate recursion

    else {
        if (currentCombination.length > 0) 
        {
            currentCombination.sort((a,b)=>{
              return a.id > b.id
            });  
            //var uniquePermutation = true;

            var tmp = currentCombination.map((cc)=>{
                  return cc.id;
               })

            if (combStrings.indexOf(JSON.stringify(tmp)) == -1) {
                this.AllCombinations.push(currentCombination);
                var tmp = currentCombination.map((cc)=>{
                  return cc.id;
                })
                combStrings.push(JSON.stringify(tmp))
            }
        }
    }

    for (var i = 0; i < beers.length; i++) {
        var newChoices = beers.slice();       
        var newCombination = currentCombination.concat(newChoices.splice(i, 1)); 
        var newRemainingSum = remainingSum - beers[i].size;
        this.GetCombinations(newCombination, newChoices, newRemainingSum);
    }
}
GetCombinations([],Beers,TrunkSize)
console.log(AllCombinations,combStrings)

score 1 · Answer 4 · answered May 19 '17 at 07:12

You could get all combinations and decide which sets match the conditions.

function getCombinations(array, sum, length) {

    function fork(i, t) {
        var s = t.reduce((a, b) => a + b.size, 0);
        if (i === array.length) {
            return s <= sum && t.length <= length && result.push(t);
        }
        fork(i + 1, t.concat([array[i]]));
        fork(i + 1, t);
    }

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

var beers = [{ id: 1, size: 4 }, { id: 5, size: 1 }, { id: 10, size: 0.5 }, { id: 11, size: 1 }, { id: 12, size: 2 }, { id: 13, size: 1 }],
    result = getCombinations(beers, 2, 2);

document.getElementById('out').appendChild(document.createTextNode(JSON.stringify(result, 0, 4)));

<pre id="out"></pre>

Need help in getting as much unique beer as possible

4 Answers4