Fun with Combinatorics

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.

This entry was posted in Uncategorized. Bookmark the permalink.

One Response to Fun with Combinatorics

  1. RefuX says:

    It will be interesting to see what solutions are used in the future to solve the issue of many downloaded plugins.It’s definitely the case that with the more Firefox plugins I install the more frequently it crashes.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s