Click here to Skip to main content
Click here to Skip to main content
Go to top

Combinatorial algorithms in C#

, 19 Aug 2002
Rate this:
Please Sign up or sign in to vote.
Some basic combinatorial algoritms for use in the NET framework

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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

gybrush
Web Developer
Bulgaria Bulgaria
No Biography provided

Comments and Discussions

 
QuestionNice Job! PinmemberMember 39299965-Jul-12 20:42 
QuestionA recursive program in C to generate nCk PinmemberManohar Bhat20-Jan-12 9:06 
GeneralNeed help PinmemberVikas Misra(TCS)14-Oct-09 4:21 
GeneralCombinatorics... Pinmembergourmettt17-Jul-08 21:15 
GeneralLicense Issue PinmemberÖzgür Akdemirci21-Apr-08 2:40 
GeneralRe: License Issue Pinmembergybrush21-Apr-08 10:03 
GeneralRepeated Items PinmemberAndre Falci2-May-07 7:14 
GeneralUsed this to solve brainteaser Pinmemberigitur11-Apr-07 14:30 
GeneralAnother example Pinmembergeblack31-Jul-06 8:37 
GeneralTime Saver Pinmemberydrabu21-Jun-06 17:34 
QuestionNeed help in combination Pinmemberobaid_8419-Dec-05 20:05 
GeneralCard Game Help PinmemberTMcGee29-Jun-05 4:33 
GeneralRe: Card Game Help PinmemberDaniel Persson25-Jun-06 21:15 
QuestionTotal permutations? PinmemberChris Sells17-Aug-03 13:40 
AnswerRe: Total permutations? PinmemberPete Burgess18-Oct-05 3:11 
Can you generate permutations of the numbers 1-20, check which perms add up to 20 and then return those numbers *5?
 
PeteB
I wouldn't say "he's not the sharpest knife",
I'd say "he's a spoon."

GeneralNice article Pinmemberleppie22-Aug-02 9:22 
Generalarray PinmemberGoran Mitrovic20-Aug-02 12:28 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web04 | 2.8.140921.1 | Last Updated 20 Aug 2002
Article Copyright 2002 by gybrush
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid