I think this fellow is right: http://stackoverflow.com/questions/3442770/counting-placing-items-in-bins-ac... Paul On Mon, Aug 9, 2010 at 1:08 PM, Paul Reiners <paul.reiners@gmail.com> wrote:
We have a pool of items. Each item has a set of characteristics. Each characteristic is either 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?
(For what it's worth, this is a question that came up at the software company I work at. I tend to think there is no efficient solution, but I'm looking for a good argument in favor of that. (Or, even better, an efficient way of computing this.)