You'er seriously underestimating the number of additional dimensions
that would be required. If there are really about 50 base dimensions,
I think doing it this way will cause you problems.
You actually give two different sets of dimensions in your second
example. Let's look at the simpler set:
1) 10x20x50
2) 15x15x80
3) 30x35x60
4) 30x40x50
One general algorithm would go as follows:
Consider all possible combinations of 1), 2), 3), 4). For each
combination, take the minimum of each dimension among all items used.
Then eliminate duplicates and sort.
Note that if there are n items there are 2^n - 1 combinations - this
will be impossible to handle with 50 items. More on that later.
1 --> 10x20x50
1 + 2 --> 10x15x50
1 + 3 --> 10x20x50, duplicate
1 + 4 --> 10x20x50, duplicate
1 + 2 + 3 --> 10x15x50, duplicate
1 + 2 + 4 --> 10x15x50, duplicate
1 + 3 + 4 --> 10x15x50, duplicate
1 + 2 + 3 + 4 --> 10x15x50, duplicate
2 --> 15x15x80
2 + 3 --> 15x15x60
2 + 4 --> 15x15x50
2 + 3 + 4 --> 15x15x50, duplicate
3 --> 30x35x60
3 + 4 --> 30x35x50
4 --> 30x40x50
So even for this simple set you have gone from 4 options to 8.
Consider the nastier set you also suggested:
A) 10x20x50
B) 15x15x80
C) 30x40x45
D) 30x35x38
The combinations here are:
A --> 10x20x50
AB --> 10x15x50
A C --> 10x20x45
A D --> 10x20x38
ABC --> 10x15x45
AB D --> 10x15x38
A CD --> 10x20x38, duplicate
ABCD --> 10x15x38, duplicate
B --> 15x15x80
BC --> 15x15x45
B D --> 15x15x38
BCD --> 15x15x38, duplicate
C --> 30x40x45
CD --> 30x35x38
D --> 30x35x38, duplicate
so now we have gone from 4 to 11 choices. With 50 base dimensions I
would expect that you would have several hundred choices in the final
list at best (if there's a fair degree of overlap in the individual
sizes), and quite possibly thousands (if there's not).
Now, as mentioned earlier you'll need a better algorithm for handling
as many as 50 sets of dimensions. Here's one:
From your dimensions, make three lists containing the distinct X, Y
and Z values for each dimension. In each list, also store the maximum
values for the other dimensions associated with each entry. For
example, the X list for the last example would read:
10 (20) (50)
15 (15) (80)
30 (40) (45)
Take each value in the X, Y and Z lists in turn (requiring X <= Y <=
Z). Discard any combinations where the value of one component is
greater than the maximum for that component corresponding to the
selected values fo the other components. For example, the combination
15x40x50 is rejected because for X=15, the maximum value of Y is
15.(Also, for Y=40, the maximum value of Z is 45.)
This way you have, instead of 2^n - 1, only n^3 or less combinations.
(In most cases you will have substantially less because some component
values will be repeated.) For n=50, this reduces the number of
combinations to be assessed from around 1 quadrillion to 125,000 at
most (and most likely much less). This is a practical number for a
computer to do.
For small n this is less efficient than the combinations method (the
equivalence point is at n=8), and for the same example we now have 37
combinations to look at (excluding cases where X>Y or Y>Z), so I won't
give you all the details, but we wind up with the same 11 combinations
we found earlier.
Note that this method may produce some results that don't correspond
to a valid combination of options. At least, I suspect it will and I
can't see a proof that it won't, but I don't have an actual example
handy. They're most likely to arise when you have significant overlap
in sizes used. Unfortunately I don't have a clear handle on the
expected number of these; in the case where there is significant
overlap of sizes used it would also be computationally tricky to check
that a given result does correspond to a given combination of base
dimensions. So I'll leave it at that for now. |
