Counting placing items in bins according to boolean restrictions

Question

We have a pool of items. Each item has a set of characteristics. Each characteristic is a string, integer, or floating-point number. Each item is also of a particular type. Types are hierarchical.

We also have a set of bins. Each bin has a requirement, which is a boolean expression comprised of atomic expressions regarding item characteristics. These atomic expressions can be string, integer, or floating-point comparisons and type comparisons.

We wish to put the items in the bins such that each item placed in a bin satisfies the requirement of that bin. Each bin also must contain a specified number of items.

For example, we might have the following type hierarchy:

• shape
  • triangle
    • equilateral triangle
  • rectangle
    • square

We could have the following items:

• LargeRedTriangle
• type = triangle
• color = "red"
• area = 1000
• SmallShape
• type = shape
• area = 5
• LargeBlueSquare
  • type = square
  • color = "blue"
  • area = 2000

Here is an example bin:

• LargeRectangles
  • (type == rectangle) and (area > 750)
  • item count = 5

We could put LargeBlueSquare in the LargeRectangles bin. We want exactly 5 items in this bin.

Here is another example bin:

• NonBlueTriangles
  • (type == triangle) and (not (color == "blue"))
  • item count = 10

LargeRedTriangle can go in the NonBlueTriangles bin. We want exactly 10 items in this bin.

So, we have a set of items and a set of bins. The question is to find out how many ways there are to put the items in the bins while satisfying the constraints (i.e., the requirements for items in bins and the number of items in each bin). (We don't need to enumerate all the ways to do this; we only need to know how many different ways of doing this there are.)

Is there an efficient way of determining this number? Or do we just have to 'brute-force' it and try every possible combination?

Answer 1

This is an example of a Constraint Satisfaction Problem. If you have more objects than bins, you can sometimes treat the bins individually (as a poster did with the case of one bin) and multiply the counts together, or use the individual counts for each bin in some similar fashion.

Another way is to do some form of divide and conquer; for example, suppose, among all the other constraints and attributes that are present, all the objects belong to exactly one of five different classes. Then an attempt at counting can begin with enumerating all the possibilities for partially filling bins with class 1 items. Each possibility leads to ways to enumerating the wayss to fill the remaining space fully or partially with class 2 items, and so on.

Another way to process things is to bundle certain items together: fries, a burger, and a drink can (setting certain things like nutrition aside) be called a meal, and the constraints may be that enumeration is simplified if an attempt is made to pack the bins with bundled groups of items. However, you will have a hard time getting nice lower and upper bounds that are close if you have any reasonable complexity in your constraints. If your constraints are such that there are very few ways to pack some of the bins, then a depth first search approach which packs those bins first may give you a good handle on approximate counts.

Besides Constraint Satisfaction Problem, you might try Polya Enumeration, reduction to one of a number of basic counting problems, Inclusion-Exclusion formula, and topics in enumerative combinatorics.

Good Luck.

Answer 2

See Moron's answer to this question on StackOverflow.

If I understood correctly your problem boils down to the problem of finding the number of Perfect Matchings in a bipartite graph.

Items form the left set. Bins form the right. If a bin needs k items, you make k copies of that bin.

Now you form an edge between an item and a bin if the item is a possible candidate for the bin.

Now you need to find number of perfect matchings in this graph.

Unfortunately, this is a hard problem. Calculating the number of perfect matchings in a graph is equivalent to finding the Permanent of an associated matrix, which is #P-Complete. See: Computation of the Permanent.

Your best bet might be randomized/approximation algorithms.

Answer 3

If you only have one bin, it's actually quite easy. Let N be how many items qualify to go into the bin, and K be the number of items the bin is required to have. Your answer would be nCr(N, K). The nCr (a.k.a. binomial coefficient) function is defined as:

               n!
nCr n k = ------------
           k! * (n-k)!

($n!$ means $n$ factorial)

As for multiple bins, I doubt that knowledge of the type hierarchy or the predicates in detail will be needed to make it efficient (but I may be wrong). The approach I'd take is to, for each item, list all the bins that item qualifies for. Then, just find out how many combinations of filled-up bins you get.

Sorry I don't have the answer to having multiple bins (yet), but I hope this gets you started.