[math-fun] Combinatorics question: 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 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.)
On 8/9/10, Paul Reiners <paul.reiners@gmail.com> wrote:
... (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.)
Having recently suffered a certain amount of humiliation at another site, I'm reluctant to sound unwelcoming concerning this enquiry; but I feel obliged to express some reservations. To begin with, while I not aware of harbouring any fundamentalist objections to tackling applied problems in general, this particular one doesn't sound much like any sort of "fun" to me --- but that's perhaps a matter of opinion. More seriously, if any less battle-scarred combinatorialist out there does nonetheless feel inspired to get involved, caution should be exercised to ensure that the ground rules are agreed beforehand. Some, particularly smaller, commercial outfits are liable to take a buccaneering attitude towards intellectual property. Lulled by their pleasant informality, the gullible academic devotes time and expertise to the project, to be left at its successful conclusion without so much as an acknowledgement. [Of course, such exploitation is not unknown elsewhere --- but at least in an academic environment it is actively discouraged, and on average a two-way exchange of some kind can reasonably be expected.] Fred Lunnon
I suppose you're right. *I* don't get all that much credit for the things I do myself at work. Oh, well. Paul On Mon, Aug 9, 2010 at 1:56 PM, Fred lunnon <fred.lunnon@gmail.com> wrote:
On 8/9/10, Paul Reiners <paul.reiners@gmail.com> wrote:
... (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.)
Having recently suffered a certain amount of humiliation at another site, I'm reluctant to sound unwelcoming concerning this enquiry; but I feel obliged to express some reservations.
To begin with, while I not aware of harbouring any fundamentalist objections to tackling applied problems in general, this particular one doesn't sound much like any sort of "fun" to me --- but that's perhaps a matter of opinion.
More seriously, if any less battle-scarred combinatorialist out there does nonetheless feel inspired to get involved, caution should be exercised to ensure that the ground rules are agreed beforehand.
Some, particularly smaller, commercial outfits are liable to take a buccaneering attitude towards intellectual property. Lulled by their pleasant informality, the gullible academic devotes time and expertise to the project, to be left at its successful conclusion without so much as an acknowledgement.
[Of course, such exploitation is not unknown elsewhere --- but at least in an academic environment it is actively discouraged, and on average a two-way exchange of some kind can reasonably be expected.]
Fred Lunnon
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
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.)
You lose some, you win some. WFL On 8/9/10, Paul Reiners <paul.reiners@gmail.com> wrote:
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.)
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (2)
-
Fred lunnon -
Paul Reiners