Counting placing items in bins according to boolean restrictions

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 e开发者_StackOverflowxactly 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?

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. Caculating 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.