Complex Combinatorial Algorithms

Question

So Wendy's advertises their sandwich as having 256 combinations - meaning there are 8 ingredients you can either have to not have (although I wonder why they would count the combination where you include nothing as valid, but I digress).

A generalized approach allows you to multiply the various states of each selection together, which allows more complex combinations. In this case Wendy's items can only be included or excluded. But some sandwiches might have the option of two kinds of mustard (but not both, to save costs).

These are fairly straightforward. You multiply the number of options together, so For Wendy's it's:

2*2*2*2*2*2*2*2 = 256

If they diversified their mustard selection as above it would be:

2*2*3*2*2*2*2*2 = 384

Going further appears to be harder.

If you make sesame seeds a separate item, then they require the bun item. You can have the sesame seed only if you include the bun, and you can have the bun without sesame seeds, but you cannot have sesame seeds without the bun. This can be simplified to a single bun item with three states (none, bun with seeds, bun without) but there are situations where that cannot be done.

Dell's computer configurator, for instance, disallows certain combinations (maybe the slots are all full, items are incompatible when put into same system, etc).

• What are the appropriate combinatorial approaches when dealing with significantly more complex systems where items can conflict?
• What are good, generalized, approaches to storing such information without having to code for each product/combination/item to catch conflicts?
• Is there a simple way to say, "there are X ways to configure your system/sandwich" when the system has to deal with complex conflicting combinations?

Answer 1

HP's high-end server manufacturing facility in California used a custom rule-based system for many years to do just this.

The factory shopfloor build-cycle process included up-front checks to ensure the order was buildable prior to releasing it to the builders and testers.

One of these checks determined whether the order's bill of materials (BOM) conformed to a list of rules specified by the process engineers. For example, if the customer orders processors, ensure they have also ordered sufficient dc-converter parts; or, if they have ordered a certain quantity of memory DIMMs, ensure they have also ordered a daughter-board to accommodate the additional capacity.

A computer science student with a background in compilers would have recognized the code. The code parsed the BOM, internally generating a threaded tree of parts grouped by type. It then applied the rules to the internal tree to make the determination of whether the order conformed.

As a side-effect, the system also generated build documentation for each order which workers pulled up as they built each system. It also generated expected test results for the post-build burn-in process so the testing bays could reference them and determine whether everything was built correctly.

Answer 2

"Generating Functions" comes to mind as one construct that can be used when solving this type of problem. I'd note that there are several different generating functions depending on what you want.

In North America, car license plates can be an interesting combinatorial problem in counting all the permutations where there are 36 possible values for each place of the 6 or 7 that are the lengths of license plates depending on where one is getting a plate. However, some combinations are disqualified due to there being swear words or racist words in some of them that makes for a slightly harder problem. For example, there is an infamour N-word that has at least a couple of different spellings that wouldn't be allowed on license plates I'd think.

Another example would be determining all the different orders of words using a given alphabet that contains some items repeated multiple times. For example, if one wanted all the different ways to arrange the letters of say the word "letter" it isn't just 6! which would be the case of "abcdef" because there are 2 pairs of letters that make it slightly trickier to compute.

L33t can be another way to bring in more complexity in identifying inappropriate words as while a-s-s gets censored a$$ or @ss may not necessarily be treated the same way even though it is basically the same term expressed in different ways. I'm not sure if many special characters like $ or @ would appear on license plates but one could think of parental controls on web content as having to have these kinds of algorithms to identify which terms to censor.

Answer 3

As a programmer I would do the following (although I have never actually ever had to do this in real life):

• Work out the total number of combinations, usually a straight multiplication of the options as stated in your question will suffice. There's no need to store all these combinations.
• Then divide your total by the exceptions. The exceptions can be stored as just a set of rules, effectively saying which combinations are not allowed.
• To work out a total number of combinations allowable, you will have to run through the entire set of exception rules.

If you think of all your combinations as a set, then the exceptions just remove members of that set. But you don't need to store the entire set, just the exceptions, since you can calculate the size of the set quite easily.

Answer 4

You'd probably want to create a data structure that represents an individual configuration uniquely. Then each compatibility rule should be defined in a way where it can generate a set containing all the individual configurations that fail that rule. Then you would take the union of all the sets generated by all the rules to get the set of all configurations that fail the rules. Then you count the size of that set and subtract it from the size of the set all possible configurations.

The hard part is defining the data structure in a way that can be generated by your rules and can have the set operations work on it! That's an exercise for the reader, AKA I've got nothing.