Looking for a clean, efficient way to match a set of data against known patterns.

Question

Using php5.2 and MySQL 4.1.22

I've come across something that, at first, appeared simple but has since evaded me in regards to a simple, clean solution.

We have pre-defined "packages" of product. Package 1 may have products A, B and C in it. Package 2 may have A, C, D and G in it, etc. The packages range in size from 3 to 5 products.

Now, a customer can pick any 10 products available and make a "custom" package. Since we already have certain predefined packages, we'd like to build the custom package with smaller existing packages (for shipping ease) where possible.

So, for instance, a customer selects to create a 'custom package' of products A, B, C, D, E and F. We already have a predefined package that contains A, B and C called Foo. So, the order would then be Foo, D, E and F.

The catch is in having the least amount of individual items, followed by the least amount of packages. For instance:

Custom Package: A, B, C, D, E, F, G, H, I, J.

Predefined Package (1): A, B, C, D, E

Predefined Package (2): A, B, C

Predefined Package (3): D, E, F

If I simply take the largest match, then I have 1 (5pc) package and 5 individual items. Neither Package (2) nor (3) can be built with the remaining items.

If I look deeper, I find that by not building package (1) I can instead build package (2) and package (3). Which means I have 2 packages and 4 individual items (a better choice in this buisiness rule).

As I'm using MySQL, I'm under the restraint of only having one layer of sub select available (to my knowledge). So this sort will need to be performed in php. I've looked at using array_intersect() to determine matches, but every way I've found grows exponentially in regards to processing as the number of predefined packages grows linearly.

I ran this by a couple other coder friends and again, while it seemed like there should be an easy answer we all found that it wasn't as simple as it seems. So, I thought I'd post it here as a nice noodle stretcher. Thanks much in advance for your time!

Answer 1

I suggest you let the customer help. In the product selection screens, show what packaged sets are available, and let them make the combinations (priced appropriately so that the sum of onesies is enough to cover special handling).

Answer 2

The problem is generally a "hard" one (speaking in terms of computational complexity). In fact it rings some bells in the back of my head that it probably reduces to one of those classic algorithm problems like the Knapsack problem, but I can't attach a proper name to it.

However, with such a small problem space (they can only pick 10 products), it should be fairly quick to just brute-force the thing. When someone submits a custom build, just recursively attack it with all possibilities and see which one is the best.

That is, take the components they've selected, and first try to remove the components of "Package 1" from it. If that's possible, take the remaining components and try to take the components of "Package 2" from it, etc. Keep track of the best solution you've found so far as you go along.

If it's still not fast enough (but I think it probably will be, depending on how many pre-built packages you have), you could apply some dynamic programming methods to speed it up.

---

Edited to add:

Depending on the number of possibilities and how long this actually takes to run, you may want to write the code I described above, and then just go ahead and pre-compute all the solutions for every possible combination. Then when someone submits a custom build, you just have to fetch the answer instead of computing it from scratch every time.

Even if you don't want to pre-compute them all, I'd suggest storing the result every time someone does a custom build, then in the future if anyone else does the same custom build you don't have to recalculate the solution.

Answer 3

Excuse me for making your problem a bit more complicated. :-)

Though you might like pre-calculating possible solutions, or have the consumers actually choose from the predefined packages themselves: what if a predefined package is no longer in stock?

What if no solution exists to complete the order at this time? Would you then ship part of the order, and if so: would you include single items even if you know that at some later time you could select a predefined package?

And are you really sure that predefined packages will not have some "preference" assigned? Like which predefined package to select when ordering "ABCD" and predefined packages "ABC" and "BCD" exist? If, for example, you know that predefined package "ABC" is often out of stock, then maybe that will make "BCD" to be preferred whenever possible.

So: maybe you need to use some modelling in which you can easily change some hard-coded rules, rather than trying to find an automated solution. This could of course be PHP itself.