Combinatorial algorithms in C#

• Download source files - 9 Kb

Introduction

In this article will be presented a small number of classes that can be used to perform some basic combinatorial operations on collection of objects. Here you won�t find a detailed explanation of how the code works, but mainly on how to use these utility classes. The source code is small (only 4 classes in 4 files) so if you want to see how the algorithms are implemented, have a look there.

The purpose of the utilities shown here is to present the programmer with an easy way of generating all the possible combinations, permutations and variations from a collection of objects. For example, suppose that you have balls numbered from 1 to 35 put in a black box, and want to pick up 5 of them. Then the possible combinations of 5 balls to be taken from a total number of 35 are approximately 325,000. The presented classes will generate every single one of them. This is usually very handy if you have a theory of how the black box works and test all the combinations against your theory in order to figure out what is the most likely combination of 5 numbers to be drawn.

Details

First write:

using Combinatorial;

Now declare your array of integers :

Array myIntArray = Array.CreateInstance(
    Type.GetType("System.Int32"), 35);
for (int j = 0; j < myIntArray.Length; j++)
    myIntArray.SetValue(j, j);

Then make a combinatorial object to manipulates the objects in this array (in this particular case the objects are of type System.Int32) like this :

Combinations combs = new Combinations(myIntArray, 5);

Now write a cycle to generate all the possible combinations of 5 integers from 35.

while(combs.MoveNext()) {

    Array thisComb = (Array)combs.Current;

    for (int i = 0; i < thisComb.Length; i++) {
        // Just access the value. This requres boxing.

        int nVal00 = (int)thisComb.GetValue(i);
        // Just access the value. This requres no boxing.

        Object nVal01 = thisComb.GetValue(i);		
}

The Combinations, Permutations and Variations classes all support the System.Collections.IEnumerate interface, so it is very easy to cycle through them. If you want to reset these objects just call the Reset() member function. After that, all the combinations generation will start anew.

The collection that is going to be used is passed as a parameter to the constructor of the combinatorial object. This means that you cannot reinitialize the object with a new collection when you have finished using the current one, but have to create an entirely new Combinations (or some of the others) object.

There are three possible constructors :

protected CombinatorialBase(Array arrayObjects, int nKlass );
protected CombinatorialBase(IList listObjects, int nKlass );
protected CombinatorialBase(IEnumerator enumeratorObjects, 
    int nKlass );

As you can see, you can pass any collection that supports either IList or IEnumerator interfaces. Or you can pass any array of objects. This means that you can use these classes on almost every collection met in the .NET framework. Because the combinatorial classes support the IEnumerate interface itself, you actually can create constructs like : combination of combinations or permutations of combinations of variations and all the stuff like this, that you can think of. However I strongly advice you not to do so (unless for a situation with small number of combinations) because the constructor cycles through all the objects that it have to manipulate ( the objects in the collection). If you pass another combination this process can take a lot of time.

Armed with all the constructors from above we can use code like this :

double[] doubles = new double[10];
for (int j = 0; j < doubles.Length; j++)
    doubles[j] = (double)j;

// Generate the  combinations of 5  numbers from a bunch of 10

Combinations combs = new Combinations(doubles, 5);

Or like this when using ArrayList :

ArrayList myArrayList = new ArrayList(15);
for (int j = 0; j < 10; j++)
    myArrayList.Add("str"+j.ToString());

// Generate all the permutations of 10 objects.

Permutations perms = new Permutations(myArrayList);

And even some unusual constructs like this one here :

string myString = "abcdefghij";

// Generate all the possible five char combinations from the 

// letters of this string.

Combination combs = new Combination(myString.GetEnumerator(), 5);

And now a little note for those of you who would say : Hey isn�t it true that we can generate all the permutation of 5 elements, by generating all the variations of those five elements of size (class) 5 ?

This means that :

Permutations combs = new Permutations(myArrayList);

and

Variations combs = new Variations(myArrayList, myArrayList.Count);

actually do the same thing.

So why we need a Permutation object, when we have a more general Variation object? The truth is, that mathematically they do the same. But because the algorithms for generation of Combinations and Permutation are so much easier to implement than those of Variations, these two objects are the basis of this library. The Variations object actually uses the combinations and permutations to generate all the possible variations. If you need only permutations, please always use the Permutation class.

One last thing to mention : This library generates only combinations, variations and permutations without repetition. If you need repetition you have to implement it yourself. I do not have a need for such functionality right now, so probably won�t write it very soon.

Conclusion

Some may ask why haven�t I implemented the IEnumerable interface (like in the String or Array classes), but chose the IEnumerate instead. The IEnumerable interface has just one method : GetEnumerator() that returns an enumerator. Each time you request an enumerator this interface should return to you a valid enumerator over the sequence. And one very important thing : If you have requested enumerator over the same sequence previously it must not become invalid, because it still may be in use. This is impossible with the current implementation of the Combinatorial classes and I don�t see a way to easily modify this. So I supply just IEnumerate for now.