Efficiently find every combination of assigning smaller bins to larger bins

Question

Let's say I have 7 small bins, each bin has the following number of marbles in it:

var smallBins = [1, 5, 10, 20, 30, 4, 10];

I assign these small bins to 2 large bins, each with the following maximum capacity:

var largeBins = [40, 50];

I want to find EVERY combination of how the small bins can be distributed across the big bins without exceeding capacity (eg put small bins #4,#5 in large bin #2, the rest in #1).

Constraints:

• Each small bin must be assigned to a large bin.
• A large bin can be left empty

This problem is easy to solve in O(n^m) O(2^n) time (see below): just try every combination and if capacity is not exceeded, save the solution. I'd like something faster, that can handle a variable number of bins. What obscure graph theory algorithm can I use to reduce the search space?

//Brute force
var smallBins = [1, 5, 10, 20, 30, 4, 10];
var largeBins = [40, 50];

function getLegitCombos(smallBins, largeBins) {
  var legitCombos = [];
  var assignmentArr = new Uint32Array(smallBins.length);
  var i = smallBins.length-1;
  while (true) {
    var isValid = validate(assignmentArr, smallBins, largeBins);
    if (isValid) legitCombos.push(new Uint32Array(assignmentArr));
    var allDone = increment(assignmentArr, largeBins.length,i);
    if (allDone === true) break;
  }
  return legitCombos;
}

function increment(assignmentArr, max, i) {
  while (i >= 0) {
    if (++assignmentArr[i] >= max) {
      assignmentArr[i] = 0;
      i--;
    } else {
      return i;
    }
  }
  return true;
}

function validate(assignmentArr, smallBins, largeBins) {
  var totals = new Uint32Array(largeBins.length);
  for (var i = 0; i < smallBins.length; i++) {
    var assignedBin = assignmentArr[i];
    totals[assignedBin] += smallBins[i];
    if (totals[assignedBin] > largeBins[assignedBin]) {
      return false;
    }
  }
  return true;
}
getLegitCombos(smallBins, largeBins);

Answer 1

Here's my cumbersome recursive attempt to avoid duplicates and exit early from too large sums. The function assumes duplicate elements as well as bin sizes are presented grouped and counted in the input. Rather than place each element in each bin, each element is placed in only one of duplicate bins; and each element with duplicates is partitioned distinctly.

For example, in my results, the combination, [[[1,10,20]],[[4,5,10,30]]] appears once; while in the SAS example in Leo's answer, twice: once as IN[1]={1,3,4} IN[2]={2,5,6,7} and again as IN[1]={1,4,7} IN[2]={2,3,5,6}.

Can't vouch for efficiency or smooth-running, however, as it is hardly tested. Perhaps stacking the calls rather than recursing could weigh lighter on the browser.

JavaScript code:

function f (as,bs){

  // i is the current element index, c its count; 
  // l is the lower-bound index of partitioned element
  function _f(i,c,l,sums,res){

    for (var j=l; j<sums.length; j++){
      // find next available duplicate bin to place the element in
      var k=0;
      while (sums[j][k] + as[i][0] > bs[j][0]){
        k++;
      }

      // a place for the element was found          
      if (sums[j][k] !== undefined){
        var temp = JSON.stringify(sums),
            _sums = JSON.parse(temp);
        _sums[j][k] += as[i][0];

        temp = JSON.stringify(res);           
        var _res = JSON.parse(temp);

        _res[j][k].push(as[i][0]);

        // all elements were placed
        if (i == as.length - 1 && c == 1){
          result.push(_res);
          return;

        // duplicate elements were partitioned, continue to next element
        } else if (c == 1){
          _f(i + 1,as[i + 1][1],0,_sums,_res);

        // otherwise, continue partitioning the same element with duplicates
        } else {
          _f(i,c - 1,j,_sums,_res);
        }
      }
    }
  }

  // initiate variables for the recursion 
  var sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    sums[i] = [];
    res[i] = [];
    for (var j=0; j<bs[i][1]; j++){
      sums[i][j] = 0;
      res[i][j] = [];
    }  
  }

  _f(0,as[0][1],0,sums,res);
  return result;
}

Output:

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[40,1],[50,1]])));

/*
[[[[1,4,5,10,10]],[[20,30]]],[[[1,4,5,10,20]],[[10,30]]],[[[1,4,5,20]],[[10,10,30]]]
,[[[1,4,5,30]],[[10,10,20]]],[[[1,4,10,20]],[[5,10,30]]],[[[1,4,30]],[[5,10,10,20]]]
,[[[1,5,10,20]],[[4,10,30]]],[[[1,5,30]],[[4,10,10,20]]],[[[1,10,20]],[[4,5,10,30]]]
,[[[1,30]],[[4,5,10,10,20]]],[[[4,5,10,20]],[[1,10,30]]],[[[4,5,30]],[[1,10,10,20]]]
,[[[4,10,20]],[[1,5,10,30]]],[[[4,30]],[[1,5,10,10,20]]],[[[5,10,20]],[[1,4,10,30]]]
,[[[5,30]],[[1,4,10,10,20]]],[[[10,10,20]],[[1,4,5,30]]],[[[10,20]],[[1,4,5,10,30]]]
,[[[10,30]],[[1,4,5,10,20]]],[[[30]],[[1,4,5,10,10,20]]]]
*/

console.log(JSON.stringify(f([[1,1],[4,1],[5,1],[10,2],[20,1],[30,1]], [[20,2],[50,1]])));

/*
[[[[1,4,5,10],[10]],[[20,30]]],[[[1,4,5,10],[20]],[[10,30]]],[[[1,4,5],[20]],[[10,10,30]]]
,[[[1,4,10],[20]],[[5,10,30]]],[[[1,5,10],[20]],[[4,10,30]]],[[[1,10],[20]],[[4,5,10,30]]]
,[[[4,5,10],[20]],[[1,10,30]]],[[[4,10],[20]],[[1,5,10,30]]],[[[5,10],[20]],[[1,4,10,30]]]
,[[[10,10],[20]],[[1,4,5,30]]],[[[10],[20]],[[1,4,5,10,30]]]]
*/

Here's a second, simpler version that only attempts to terminate the thread when an element cannot be placed:

function f (as,bs){

  var stack = [],
      sums = [],
      res = []
      result = [];

  for (var i=0; i<bs.length; i++){
    res[i] = [];
    sums[i] = 0;
  }

  stack.push([0,sums,res]);

  while (stack[0] !== undefined){
    var params = stack.pop(),
        i = params[0],
        sums = params[1],
        res = params[2];

    for (var j=0; j<sums.length; j++){
      if (sums[j] + as[i] <= bs[j]){
        var _sums = sums.slice();
        _sums[j] += as[i];

        var temp = JSON.stringify(res);
        var _res = JSON.parse(temp);

        _res[j].push(i);

        if (i == as.length - 1){
          result.push(_res);

        } else {
          stack.push([i + 1,_sums,_res]);
        }
      }
    }
  }

  return result;
}

Output:

var r = f([1,5,10,20,30,4,10,3,4,5,1,1,2],[40,50,30]);
console.log(r.length)

console.log(JSON.stringify(f([1,4,5,10,10,20,30], [40,50])));

162137 

[[[30],[1,4,5,10,10,20]],[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]]
,[[10,30],[1,4,5,10,20]],[[10,20],[1,4,5,10,30]],[[10,10,20],[1,4,5,30]]
,[[5,30],[1,4,10,10,20]],[[5,10,20],[1,4,10,30]],[[5,10,20],[1,4,10,30]]
,[[4,30],[1,5,10,10,20]],[[4,10,20],[1,5,10,30]],[[4,10,20],[1,5,10,30]]
,[[4,5,30],[1,10,10,20]],[[4,5,10,20],[1,10,30]],[[4,5,10,20],[1,10,30]]
,[[1,30],[4,5,10,10,20]],[[1,10,20],[4,5,10,30]],[[1,10,20],[4,5,10,30]]
,[[1,5,30],[4,10,10,20]],[[1,5,10,20],[4,10,30]],[[1,5,10,20],[4,10,30]]
,[[1,4,30],[5,10,10,20]],[[1,4,10,20],[5,10,30]],[[1,4,10,20],[5,10,30]]
,[[1,4,5,30],[10,10,20]],[[1,4,5,20],[10,10,30]],[[1,4,5,10,20],[10,30]]
,[[1,4,5,10,20],[10,30]],[[1,4,5,10,10],[20,30]]]

Answer 2

This problem is seen often enough that most Constraint Logic Programming systems include a predicate to model it explicitly. In OPTMODEL and CLP, we call it pack:

proc optmodel;
    set SMALL init 1 .. 7, LARGE init 1 .. 2;
    num size    {SMALL} init [1 5 10 20 30 4 10];
    num capacity{LARGE} init [40 50];

    var WhichBin {i in SMALL} integer >= 1 <= card(LARGE);
    var SpaceUsed{i in LARGE} integer >= 0 <= capacity[i];

    con pack( WhichBin, size, SpaceUsed );

    solve with clp / findall;

    num soli;
    set IN{li in LARGE} = {si in SMALL: WhichBin[si].sol[soli] = li}; 
    do soli = 1 .. _nsol_;
        put IN[*]=;
    end;
quit;

This code produces all the solutions in 0.06 seconds on my laptop:

IN[1]={1,2,3,4,6} IN[2]={5,7}
IN[1]={1,2,3,4} IN[2]={5,6,7}
IN[1]={1,2,3,6,7} IN[2]={4,5}
IN[1]={1,2,5,6} IN[2]={3,4,7}
IN[1]={1,2,5} IN[2]={3,4,6,7}
IN[1]={1,2,4,6,7} IN[2]={3,5}
IN[1]={1,2,4,7} IN[2]={3,5,6}
IN[1]={1,2,4,6} IN[2]={3,5,7}
IN[1]={1,3,4,6} IN[2]={2,5,7}
IN[1]={1,3,4} IN[2]={2,5,6,7}
IN[1]={1,5,6} IN[2]={2,3,4,7}
IN[1]={1,5} IN[2]={2,3,4,6,7}
IN[1]={1,4,6,7} IN[2]={2,3,5}
IN[1]={1,4,7} IN[2]={2,3,5,6}
IN[1]={2,3,4,6} IN[2]={1,5,7}
IN[1]={2,3,4} IN[2]={1,5,6,7}
IN[1]={2,5,6} IN[2]={1,3,4,7}
IN[1]={2,5} IN[2]={1,3,4,6,7}
IN[1]={2,4,6,7} IN[2]={1,3,5}
IN[1]={2,4,7} IN[2]={1,3,5,6}
IN[1]={3,5} IN[2]={1,2,4,6,7}
IN[1]={3,4,7} IN[2]={1,2,5,6}
IN[1]={3,4,6} IN[2]={1,2,5,7}
IN[1]={3,4} IN[2]={1,2,5,6,7}
IN[1]={5,7} IN[2]={1,2,3,4,6}
IN[1]={5,6} IN[2]={1,2,3,4,7}
IN[1]={5} IN[2]={1,2,3,4,6,7}
IN[1]={4,6,7} IN[2]={1,2,3,5}
IN[1]={4,7} IN[2]={1,2,3,5,6}

Just change the first 3 lines to solve for other instances. However, as others have pointed out, this problem is NP-Hard. So it can switch from very fast to very slow suddenly. You could also solve the version where not every small item needs to be assigned to a large bin by creating a dummy large bin with enough capacity to fit the entire collection of small items.

As you can see from the "Details" section in the manual, the algorithms that solve practical problems quickly are not simple, and their implementation details make a big difference. I am unaware of any CLP libraries written in Javascript. Your best bet may be to wrap CLP in a web service and invoke that service from your Javascript code.