12,945,066 members (67,988 online)
alternative version

#### Stats

142.9K views
69 bookmarked
Posted 19 Aug 2002

# Combinatorial algorithms in C#

, 19 Aug 2002
 Rate this:
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++)

// 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.

A list of licenses authors might use can be found here

## Share

 Web Developer Bulgaria
No Biography provided

## You may also be interested in...

 First Prev Next
 Nice Job! Member 39299965-Jul-12 20:42 Member 3929996 5-Jul-12 20:42
 A recursive program in C to generate nCk Manohar Bhat20-Jan-12 9:06 Manohar Bhat 20-Jan-12 9:06
 Need help Vikas Misra(TCS)14-Oct-09 4:21 Vikas Misra(TCS) 14-Oct-09 4:21
 Combinatorics... gourmettt17-Jul-08 21:15 gourmettt 17-Jul-08 21:15
 License Issue Özgür Akdemirci21-Apr-08 2:40 Özgür Akdemirci 21-Apr-08 2:40
 Re: License Issue gybrush21-Apr-08 10:03 gybrush 21-Apr-08 10:03
 Repeated Items Andre Falci2-May-07 7:14 Andre Falci 2-May-07 7:14
 Used this to solve brainteaser igitur11-Apr-07 14:30 igitur 11-Apr-07 14:30
 Another example geblack31-Jul-06 8:37 geblack 31-Jul-06 8:37
 Time Saver ydrabu21-Jun-06 17:34 ydrabu 21-Jun-06 17:34
 Need help in combination obaid_8419-Dec-05 20:05 obaid_84 19-Dec-05 20:05
 Card Game Help TMcGee29-Jun-05 4:33 TMcGee 29-Jun-05 4:33
 I would like to use this library to help me evaluate a Gin Rummy Hand. For instance if I have the following cards Ah, 2h, 3h, 7c, 7s, 7d, 8s, 9s, Jd, Kh. Then I want to get the following combinations {Ah,2h,3h}, {7c,7s,7d}, {7s,8s,9s}. I can then determine which combinations give me the best hand. Any help would be greatly appreciated. Thanks, McGee
 Total permutations? Chris Sells17-Aug-03 13:40 Chris Sells 17-Aug-03 13:40
 Re: Total permutations? Pete Burgess18-Oct-05 3:11 Pete Burgess 18-Oct-05 3:11
 Nice article leppie22-Aug-02 9:22 leppie 22-Aug-02 9:22
 array Goran Mitrovic20-Aug-02 12:28 Goran Mitrovic 20-Aug-02 12:28
 Last Visit: 31-Dec-99 18:00     Last Update: 23-May-17 7:49 Refresh 1