Permutations in Testing

Permutations are one of the most important concepts in software testing. A permutation is a rearrangement. For example, a string permutation is a rearrangement of strings — if you start with { "ant", "bat", "cow" }, then there are a total of 6 permutations:

 

{ "ant", "bat", "cow" }

{ "ant", "cow", "bat" }

{ "bat", "ant", "cow" }

{ "bat", "cow", "ant" }

{ "cow", "ant", "bat" }

{ "cow", "bat", "ant" }

 

One of the reasons why permutations are so important in software engineering is that because all software systems ultimately boil down to a set of inputs, some processing, and a set of outputs, you cannot assume the inputs are in a particular order and you must test your system by feeding it all permutations of inputs. The ability to programmatically generate permutations is a fundamental software engineering skill and is actually quite tricky. The basic operations on string permutations are: creating the first permutation element, generating the successor element for a given element, determining the last permutation in a set, determining the total number of permutations for an initial set of strings, and generating the kth permutation element for a given initial set of strings. My article "String Permutations" in the December 2006 issue of MSDN Magazine (see http://msdn.microsoft.com/msdnmag/issues/06/12/TestRun) has a detailed explanation of these basic operations.