Click here to Skip to main content
15,867,330 members
Articles / Programming Languages / C#
Article

Combinatorial algorithms in C#

Rate me:
Please Sign up or sign in to vote.
4.88/5 (28 votes)
19 Aug 20024 min read 172.9K   2.4K   69   17
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:

C#
using Combinatorial;

Now declare your array of integers :

C#
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 :

C#
Combinations combs = new Combinations(myIntArray, 5);

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

C#
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 :

C#
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 :

C#
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 :

C#
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 :

C#
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 :

C#
Permutations combs = new Permutations(myArrayList);

and

C#
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


Written By
Web Developer
Bulgaria Bulgaria
This member has not yet provided a Biography. Assume it's interesting and varied, and probably something to do with programming.

Comments and Discussions

 
QuestionNice Job! Pin
erkan_mrs5-Jul-12 20:42
erkan_mrs5-Jul-12 20:42 
QuestionA recursive program in C to generate nCk Pin
Manohar Bhat20-Jan-12 9:06
Manohar Bhat20-Jan-12 9:06 
GeneralNeed help Pin
Vikas Misra(TCS)14-Oct-09 4:21
Vikas Misra(TCS)14-Oct-09 4:21 
GeneralCombinatorics... Pin
gourmettt17-Jul-08 21:15
gourmettt17-Jul-08 21:15 
Hi!

I need a Method that performs something like this:
I have x searchparameter (A and B) and y fields (a,b,c (eg. FirstName, LastName, MiddleName)) that can be searched for:
My Querystring should look like indicated in the table:


Where    (a)                (b)                (c)
         like     and       like       and     like
   --------------------------------------------------------------------
       (A&B)                                               |    or
                            (A&B)                          |    or
                                                (A&B)      |    or
       (A)                  (B)                            |    or
       (B)                  (A)                            |    or
       (A)                                      (B)        |    or
       (B)                                      (A)        |    or
                            (A)                 (B)        |    or
                            (B)                 (A)        |    or


I´m really stuck, any hint is much appreciated:
wirth@jos.zzn.com

Thank you all!
GeneralLicense Issue Pin
Özgür Akdemirci21-Apr-08 2:40
Özgür Akdemirci21-Apr-08 2:40 
GeneralRe: License Issue Pin
gybrush21-Apr-08 10:03
gybrush21-Apr-08 10:03 
GeneralRepeated Items Pin
Andre Falci2-May-07 7:14
Andre Falci2-May-07 7:14 
GeneralUsed this to solve brainteaser Pin
Francois Botha11-Apr-07 14:30
Francois Botha11-Apr-07 14:30 
GeneralAnother example Pin
geblack31-Jul-06 8:37
geblack31-Jul-06 8:37 
GeneralTime Saver Pin
ydrabu21-Jun-06 17:34
ydrabu21-Jun-06 17:34 
QuestionNeed help in combination Pin
obaid_8419-Dec-05 20:05
obaid_8419-Dec-05 20:05 
GeneralCard Game Help Pin
TMcGee29-Jun-05 4:33
TMcGee29-Jun-05 4:33 
GeneralRe: Card Game Help Pin
Daniel Persson25-Jun-06 21:15
Daniel Persson25-Jun-06 21:15 
QuestionTotal permutations? Pin
Chris Sells17-Aug-03 13:40
Chris Sells17-Aug-03 13:40 
AnswerRe: Total permutations? Pin
Pete Burgess18-Oct-05 3:11
Pete Burgess18-Oct-05 3:11 
GeneralNice article Pin
leppie22-Aug-02 9:22
leppie22-Aug-02 9:22 
Generalarray Pin
Goran Mitrovic20-Aug-02 12:28
Goran Mitrovic20-Aug-02 12:28 

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

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