I came across a pair of interesting articles today on MSDN. In them, the author shows how to put together a class that would assist in generating combinations. Here combination is used in its mathematical sense, meaning an unordered arrangement of objects (differing from permuations where order does matter). You specify how many total items you have and how many of those items you would like in each subset, and it will tell you how many possible unique subsets you can make and the elements in each of the sets. Typically you come across this stuff if you take a statistics course or if you had an algebra class that went into probability.
What i found most interesting about the articles, was how the author deviated from the standard formulas you might have learned in your math classes to use more efficient algorithms that do the same thing. The first article looks at (among other things) calcuating the total number of combinations. That processes traditionally involves very large numbers (thanks to all the factorials), but the process was rewritten to avoid the potential data overflows that would otherwise occur with large sets of data. The second article looks at finding the m-th combination in the series of possible values. One way to do that would be to loop m number of times, essentially adding 1 each time, but again that can take quite a while with large sets. The author uses some very interesting math principles (specifically something called a "combinadic") to make quick work of the task.
This type of stuff makes me excited about taking more math classes at GVSU. It would be fun to tackle a programming challenge like this for once rather than putting together another HTML form that dumps its contents into a database.
Posted by Matthew at August 2, 2004 12:46 PM