11,923,948 members (64,938 online)
alternative version

17.8K views
9 bookmarked
Posted

# A C# Combinations Iterator

, 16 Nov 2009 CPOL
 Rate this:
An iterator over all combinations of (m) elements from a sequence of (n) elements

## Introduction

In my previous article, 'A C# Permutation Iterator', I presented a compact way to permutate over a sequence. In this article, I will expand my iterator to include combinations.

## Using the Code

This iterator works recursively. The recursion terminal condition is when we elect to choose 0 elements, in which case the sequence is returned as is. In the recursive case, it is a bit more complex than the permutation iterator. The algorithm works by holding the first element, and making a recursive call on the rest of the sequence. This is done iteratively (n) times where (n) is the length of the sequence. However, each progressive iteration calls the recursion with an ever decreasing sequence length. As an example, here is a depiction of the process when choosing 2 elements from a sequence of 5 (the result of each iteration is the first 2 elements):

 Sequence yielded Comments Result (the first 2 elements) 12345 The initial sequence and first result 12 13452 Inner rotation (starting at the 2nd element) 13 14523 Inner rotation 14 15234 Inner rotation 15 23451 Outer rotation 23 24531 Inner rotation - Note that the last element is now excluded from the rotation 24 25341 Inner rotation 25 34512 Outer rotation 34 35412 Inner rotation - Note how the last two elements are now excluded from the rotation 35 45123 Outer rotation 45

And here is the code:

```private static void RotateLeft<T>(IList<T> sequence, int start, int count)
{
T tmp = sequence[start];
sequence.RemoveAt(start);
sequence.Insert(start + count - 1, tmp);
}

public static IEnumerable<IList<T>> Combinations<T>(
IList<T> sequence,
int start,
int count,
int choose)
{
if (choose == 0) yield return sequence;
else
{
for (int i = 0; i < count; i++)
{
foreach (var perm in Combinations(
sequence,
start + 1,
count - 1 - i,
choose - 1))
yield return perm;
RotateLeft(sequence, start, count);
}
}
}```

Note that each iteration returns a full length sequence, however the result is actually contained in the first (m) elements, where (m) is the number of elements we elected to choose from the sequence.

The initial call to the `Combinations `function should pass `0 `as the `start` parameter and the sequence length as the `count` parameter. To make it easier, we can overload the call thus:

```public static IEnumerable<IList<T>> Combinations<T>(
IList<T> sequence,
int choose)
{
return Combinations(sequence, 0, sequence.Count, choose);
}```

Following is an example of iterating over combinations of 3 characters over the `string `"`abcdef`". Note how I am using the `Take` extension method to grab only the result part from the iteration result.

```private static void CombinationsOverString(string s, int count)
{
foreach (var comb in Iterator.Combinations(s.ToCharArray().ToList(), count))
{
string r = new string(comb.Take(count).ToArray());
Console.Write("{0,-8}", r);
}
Console.WriteLine();
}```

Output:

```abc     abd     abe     abf     acd     ace     acf     ade     adf     aef
bcd     bce     bcf     bde     bdf     bef     cde     cdf     cef     def```

And here is an example of permutations over these combinations using the permutation iterator from my previous article.

```private static void CombinationsPermutations(string s, int count)
{
foreach (var combo in Iterator.Combinations(
s.ToCharArray().ToList(),
count))
{
foreach (var permu in Iterator.Permutations(combo, count))
{
string r = new string(permu.Take(count).ToArray());
Console.Write("{0,-8}", r);
}
}
Console.WriteLine();
}```

Output:

```abc     bac     cab     acb     bca     cba     abd     bad     dab     adb
bda     dba     abe     bae     eab     aeb     bea     eba     abf     baf
ace     cae     eac     aec     cea     eca     acf     caf     fac     afc
fad     afd     dfa     fda     aef     eaf     fae     afe     efa     fea
bcd     cbd     dbc     bdc     cdb     dcb     bce     cbe     ebc     bec
ceb     ecb     bcf     cbf     fbc     bfc     cfb     fcb     bde     dbe
ebd     bed     deb     edb     bdf     dbf     fbd     bfd     dfb     fdb
bef     ebf     fbe     bfe     efb     feb     cde     dce     ecd     ced
dec     edc     cdf     dcf     fcd     cfd     dfc     fdc     cef     ecf
fce     cfe     efc     fec     def     edf     fde     dfe     efd     fed```

## Points of Interest

There are many implementations of combination and permutation iterators to be found on the internet, however I particularly like this one due to the fact that it is light on memory, and doesn't create any unnecessary objects. The corollary of this, is that the sequence is modified while the iterator is running; if this is not desired, the iteration should be run on a copy of the original sequence.

## History

• 16-Nov-2009 - Initial posting

## Share

 Software Developer (Senior) Israel
Software developer since 1984, currently specializing in C# and .NET.

## You may also be interested in...

 First Prev Next
 I like this NightJammer16-Nov-09 22:56 NightJammer 16-Nov-09 22:56
 Recursion PIEBALDconsult16-Nov-09 5:56 PIEBALDconsult 16-Nov-09 5:56
 Re: Recursion PIEBALDconsult16-Nov-09 9:22 PIEBALDconsult 16-Nov-09 9:22
 Re: Recursion [modified] mb1816-Nov-09 11:31 mb18 16-Nov-09 11:31
 Re: Recursion PIEBALDconsult16-Nov-09 15:38 PIEBALDconsult 16-Nov-09 15:38
 Re: Recursion Lee N Middleton6-Dec-10 7:12 Lee N Middleton 6-Dec-10 7:12
 Re: Recursion PIEBALDconsult6-Dec-10 15:08 PIEBALDconsult 6-Dec-10 15:08
 Re: Recursion Lee N Middleton7-Dec-10 6:02 Lee N Middleton 7-Dec-10 6:02
 Re: Recursion PIEBALDconsult7-Dec-10 19:13 PIEBALDconsult 7-Dec-10 19:13
 Last Visit: 31-Dec-99 19:00     Last Update: 25-Nov-15 22:18 Refresh 1