Bin packing bruteforce without duplicates and empty bins

Question

I want to find all ways to distribute n elements to b bins but without "duplicates" and empty bins.

Example

If I have n = 3 elements and b = 2 bins and apply the bruteforce method from this stackoverflow thread Bin packing bruteforce method I get these results:

[[0, 1, 2, 3], []]
[[0, 1, 2], [3]]
[[0, 1, 3], [2]]
[[0, 1], [2, 3]]
[[0, 2, 3], [1]]
[[0, 2], [1, 3]]
[[0, 3], [1, 2]]
[[0], [1, 2, 3]]
[[1, 2, 3], [0]]
[[1, 2], [0, 3]]
[[1, 3], [0, 2]]
[[1], [0, 2, 3]]
[[2, 3], [0, 1]]
[[2], [0, 1, 3]]
[[3], [0, 1, 2]]
[[], [0, 1, 2, 3]]

Definition of "duplicates"

Half of the results are duplicates. Only the order of the bins is switched: First and last is the same, 2nd and 2nd to last is the same, etc...

Definition of empty bins

I don't want any bins to be empty. If you look at the previous example the first and the last line have an empty bin.

So you want to add a validation step? If so, then show your code so that it will be possible to add that step. — Amit, Jul 26 '15 at 10:41
I'd rather create an algorithm that inherently produces only solutions that fulfill the criteria from above instead of dropping solutions after creating every possible solution. The algorithm that I used for the results above is taken as is from the [linked stackoverflow thread](http://stackoverflow.com/questions/16083977/bin-packing-bruteforce-method). — conscho, Jul 26 '15 at 10:48
@conscho your question is not clear. classical `bin-packing` tries to minimize the number of bins. In your case, you want to find all ways to distribute `n` items into `b` bins, isn't it? — Karthik, Jul 26 '15 at 11:26
The thing you want is closely connected to symmetry-breaking. This paper [Discussion about Constraint Programming Bin Packing Models](https://www.aaai.org/ocs/index.php/WS/AAAIW11/paper/viewFile/3817/4221) lists the constraints needed to achieve this. But this may not be easy to add to your code, because these constraints are tailored for the Constraint-Programming approach, which i can recommend. — sascha, Jul 26 '15 at 11:26
@karthik you are absolutely right. I updated the description. — conscho, Jul 26 '15 at 14:10
@conscho you want to print the ways or finding the number is enough? — Karthik, Jul 26 '15 at 14:14
Seems closely related to the theory of unordered integer partitions. Look into *Stirling numbers of the second kind* — John Coleman, Jul 26 '15 at 14:18

John Coleman · Accepted Answer · 2015-07-26T17:30:46.483

The number of such partitions is called a Stirling number of the second kind. The Wikipedia article on these numbers gives a recurrence relation which can be modified to give a recursive function for generating these partitions. The following Python implementation uses memoization to keep the computation feasible:

def add(a,p,i):
    #adds a to the ith cell of partition p
    #returns a new partiton
    return [piece + [a] if j == i else piece for j, piece in enumerate(p)]

def addToAll(a,p):
    #adds a to all pieces of p
    #returns a list of partitions
    return [add(a,p,i) for i in range(len(p))]

def partition(n,k):
    memoDict = {}
    def helperPart(n,k):
        if n == 0 and k == 0: return [[]]
        elif n == 0 or k == 0: return []
        elif (n,k) in memoDict:
            return memoDict[(n,k)]
        else:
            kParts = helperPart(n-1,k)
            kMinusParts = helperPart(n-1,k-1)
            parts = [part + [[n]] for part in kMinusParts]
            for p in kParts:
                parts.extend(addToAll(n,p))
            memoDict[(n,k)] = parts
            return parts
    return helperPart(n,k)

For example:

>>> partitions = partition(5,3)
>>> for p in partitions: print(p)

[[1, 2, 3], [4], [5]]
[[1, 2, 4], [3], [5]]
[[1, 2], [3, 4], [5]]
[[1, 3, 4], [2], [5]]
[[1, 3], [2, 4], [5]]
[[1, 4], [2, 3], [5]]
[[1], [2, 3, 4], [5]]
[[1, 2, 5], [3], [4]]
[[1, 2], [3, 5], [4]]
[[1, 2], [3], [4, 5]]
[[1, 3, 5], [2], [4]]
[[1, 3], [2, 5], [4]]
[[1, 3], [2], [4, 5]]
[[1, 5], [2, 3], [4]]
[[1], [2, 3, 5], [4]]
[[1], [2, 3], [4, 5]]
[[1, 4, 5], [2], [3]]
[[1, 4], [2, 5], [3]]
[[1, 4], [2], [3, 5]]
[[1, 5], [2, 4], [3]]
[[1], [2, 4, 5], [3]]
[[1], [2, 4], [3, 5]]
[[1, 5], [2], [3, 4]]
[[1], [2, 5], [3, 4]]
[[1], [2], [3, 4, 5]]

It is reasonably efficient: it takes less than a second to generate the 42,525 partitions of 10 objects into 5 bins.

score 0 · Answer 2 · edited May 23 '17 at 12:31

It seems like I found a solution myself.

I adapted the Ruby code from this stackoverflow answer to fit my needs:

class Array
  def distribute_to_bins(bins_left)
    Enumerator.new do |yielder|
      if self.empty?
        yielder.yield([])
      else

        # If there is only one bin left, fill all remaining items in it
        min_elements_in_bin = if bins_left == 1
                                self.size
                              else
                                1
                              end
        # Make sure that there are sufficient items left to not get any empty bins
        max_elements_in_bin = self.size - (bins_left - 1)

        (min_elements_in_bin..max_elements_in_bin).to_a.each do |number_of_elements_in_bin|
          self.drop(1).combination(number_of_elements_in_bin - 1).map { |vs| [self.first] + vs }.each do |values|
            (self - values).distribute_to_bins(bins_left - 1).each do |group|
              yielder.yield([values] + group)
            end
          end
        end
      end
    end
  end
end

Execution like so:

pp (1..5).to_a.distribute_to_bins(3).to_a

Will yield all possibilities without empty bins nor duplicates:

[[[1], [2], [3, 4, 5]],
 [[1], [2, 3], [4, 5]],
 [[1], [2, 4], [3, 5]],
 [[1], [2, 5], [3, 4]],
 [[1], [2, 3, 4], [5]],
 [[1], [2, 3, 5], [4]],
 [[1], [2, 4, 5], [3]],
 [[1, 2], [3], [4, 5]],
 [[1, 2], [3, 4], [5]],
 [[1, 2], [3, 5], [4]],
 [[1, 3], [2], [4, 5]],
 [[1, 3], [2, 4], [5]],
 [[1, 3], [2, 5], [4]],
 [[1, 4], [2], [3, 5]],
 [[1, 4], [2, 3], [5]],
 [[1, 4], [2, 5], [3]],
 [[1, 5], [2], [3, 4]],
 [[1, 5], [2, 3], [4]],
 [[1, 5], [2, 4], [3]],
 [[1, 2, 3], [4], [5]],
 [[1, 2, 4], [3], [5]],
 [[1, 2, 5], [3], [4]],
 [[1, 3, 4], [2], [5]],
 [[1, 3, 5], [2], [4]],
 [[1, 4, 5], [2], [3]]]

Bin packing bruteforce without duplicates and empty bins

2 Answers2

Linked