Page 2 of 2   « previous page

The Choose() Method
The last method in my class is one that returns the total number of combination elements for specified values of set size n and subset size k as you can see in Listing 4.

In mathematics this function is often called Choose() so I use it here too. Recall from the beginning of this article that Choose(5,3) returns the number of combination elements of 5 strings taken 3 at time. I declare the function as Shared because it's not really tied to a particular instance of a StringCombination element; so when I call the function I'll call it as StringCombination.Choose(5,3) rather than instantiating a StringCombination object (say c, for example) and calling as c.Choose(5,3). First, I check my input parameters to make sure their values aren't zero or negative. This is arbitrary to some extent and you may want to modify your definition of Chosse(n,k) if n or k or both are zero.

Now, the mathematical definition of Choose(n,k) is n! / (n! * (n-k)!) where n! is "n factorial." You might recall from a math course that 3! = 3 * 2 * 1 = 6, and 4! = 4 * 3 * 2 * 1 = 24, and so on. Implementing a Choose method from the math definition is a very bad approach because the value of n! gets very, very large, very quickly. For example, the value of 64! is 64 * 63 * 62 * . . . * 1 = 126,886,932,100,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000, 000,000,000,000,000,000,000 - approximately.

With the Visual Basic.NET-type Integer, the longest factorial that can be stored without overflow is only 12!

Anyway, the point is that if you use factorial calculations, your intermediate results will likely overflow even for small values of n and k. A better algorithm is to use an alternative definition of Choose():

Choose(n,k) = (n * (n-1) * (n-2) * . . . * (n-k+1)) / (1 * 2 * . . . * k).

For example, Choose(5,3) = (5 * 4 * 3) / (1 * 2 * 3) = 60/6 = 10. The idea is to compute partial products and divide as you go rather than compute two huge numbers and divide them. A second optimization for the Choose() implementation comes from the fact that, as it turns out:

Choose(n,k) = Choose(n, n-k).

For example, Choose(20,17) = Choose(20,3).

This isn't an obvious relation but if you work out a few examples on paper you'll see why it's true. Calculating Choose(20,17) involves 16 partial products and divisions, but calculating the equivalent Chose(20,3) requires only two partial products and divisions. Putting these ideas leads to the implementation of Choose() above. I use the variable diff to hold the difference between n and k, and I use the variable newk to hold the smaller of k and n-k.

I'll leave it to you to walk through a couple of examples to see the other details of exactly how the algorithm works.

Using the StringCombination Class
With the StringCombination class implemented as described and saved as StringCombinationsLib, you can easily create and manipulate string combinations. For example, you can create a new Visual Studio Console Application program. Then add a project reference to the StringCombinationsLib and an Imports StringCombinationsLib statement. With that done you can write code like:

Dim items As String() = New String() {"alpha", "beta", "delta", "gamma"}
Console.WriteLine("Number of 4 items taken 2 at a time is " &
    StringCombination.Choose(4, 2))
Dim c1 As StringCombination = New StringCombination(items, 2)
Console.WriteLine("The initial element is " & c1.ToString())
Dim c2 = c1.Successor()
Console.WriteLine("The next element is " & c2.ToString())

And to print all string combination elements you can write code like this:

Dim items As String() = New String() {"alpha", "beta", "delta", "gamma"}
Dim c As StringCombination = New StringCombination(items, 2)

While Not c Is Nothing
    Console.WriteLine(c.ToString())
    c = c.Successor
End While

Notice that at the end of the While loop, the string combination object c will have value Nothing, so you'll have to re-instantiate it if you want to use it further.

Discussion, References, and Conclusion
String combinations have a wide range of use in development, testing, and management. For example, suppose you're a tester and you have to feed three string arguments to a function under test. If you have a pool of five possible strings, you can use the code in this article to generate the 10 possible test case input sets programmatically.

Or suppose you're a program/project manager and you have to look at hardware/software configuration combinations of an operating system (Windows 98, Windows 2000, Windows XP), RAM (128MB, 256MB), and so on. You can programmatically generate configuration scenarios rather than try to grind them out manually.

The number of situations where you can use string combinations is absolutely enormous once you start looking for them.

The code I've presented here is designed for maximum flexibility and ease of modification rather for than efficiency. Consider the overall class design, for example. Notice that each instance of a StringCombination class has the exact same orig array that holds the original strings. You might want to consider modifying the design by making the orig array Shared like so:

Private Shared orig As String() = Nothing

With this approach, there's only one orig array that's shared by all instances of the StringCombination class. If you are a C# programmer, Shared is the Visual Basic.NET equivalent of a static class field. Unfortunately, if you use this design you can only have a particular flavor of StringCombination objects in scope at any given time. In other words, if you create a string object with five animal strings then in the same program scope create a second string object with four color strings, the shared orig array will conflict. It turns out that this is actually a very nasty but very interesting design problem - perhaps the topic of another article.

To summarize, string combinations are subsets of a set of strings where order doesn't matter. String combinations have a wide range of use in many areas of the software development process. The code presented in this article lets you programmatically create and manipulate string combinations and determine the total number of combination elements for a given set size n and subset size k.

References
You can find out more about combinations from many online and printed resources. An article that describes the use of mathematical combinations in software testing and gives C# source code is at http://msdn.microsoft.com/msdnmag/issues/04/07/TestRun/.

An article that describes the very tricky algorithm of how to generate a particular combination element without having to iterate from the first element is at http://msdn.microsoft.com/library/default.asp?url=/ library/en-us/dv_vstechart/html/mth_lexicograp.asp.

An article that describes mathematical permutations, a close cousin to combinations, is at http://msdn.microsoft.com/library/default.asp?url=/ library/en-us/dnnetsec/html/permutations.asp.

And an extensive discussion of both combinations and permutations is presented in Chapter 10 of my book .NET Test Automation Recipes: A Problem-Solution Approach, Apress, 2006: www.apress.com/book/bookDisplay.html?bID=10119.

Page 2 of 2   « previous page