• Share this article:

Fun with Combinatorics

Monday, October 3, 2005 - 10:10 by Wayne Beaton

I attended a talk a few days ago in which the speaker was talking about some of the challenges faced by organizations building plug-ins. He stated something to the effect of “if you have six separately deployable (i.e. not interdependent) plug-ins, then there are ‘six factorial‘ (6 x 5 x 4 x 3 x 2 x 1 = 720) different ways to deploy them”. The statement bothered me, primarily because I’m a huge nerd and mathematical genius wannabe. In fact, if you have six different plug-ins that have no interdependences and so can be deployed in any combination, you really only have at most 26 – 1 = 63 different combinations. The breakdown is pretty simple: in each combination of plug-ins, you either include or do not include each plug-in. The -1 is added because you don’t care about the combination that includes none of the plug-ins. 63 seems like a big number (and it is), but it’s nowhere near as big as 720.

Why do I care? Like I said, I’m a huge nerd. That, and implication is that testing combinations of features can be really time consuming. Even if the plug-ins you’re testing have no interdependencies, they may have common dependencies that need to be tested. Two plug-ins might, for example, manipulate the same set of resources in the workspace. These two (hypothetical) plug-ins can exist without each other, but may stomp on the shared resources when deployed together. In short, they really need to be tested together. So… for these two plug-ins, there are at most three different scenarios that need to be tested: one test to ensure that the first feature works, one to ensure that the second one works, and a final test to ensure that they work together. The fourth possible combination of the plug-ins (neither of them is deployed) isn’t all that interesting (and is tested by other folks).

Of course, a combinatorial explosion occurs as you increase the number of plug-ins (every one you add doubles the number of potentially valid combinations).

So, for a collection of n separately deployable plug-ins there are at most 2n – 1 combinations to test. Pragmatically, it is likely the case that most of these combinations can be excluded from testing by doing some dependency analysis.