Click here to Skip to main content
15,868,016 members
Articles / Programming Languages / C#

A C# Combinations Iterator

Rate me:
Please Sign up or sign in to vote.
4.17/5 (5 votes)
16 Nov 2009CPOL2 min read 38.3K   345   10   12
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 yieldedCommentsResult (the first 2 elements)
12345The initial sequence and first result12
13452Inner rotation (starting at the 2nd element)13
14523Inner rotation14
15234Inner rotation15
23451Outer rotation23
24531Inner rotation - Note that the last element is now excluded from the rotation24
25341Inner rotation25
34512Outer rotation34
35412Inner rotation - Note how the last two elements are now excluded from the rotation35
45123Outer rotation45

And here is the code:

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

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

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

C#
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
fab     afb     bfa     fba     acd     cad     dac     adc     cda     dca
ace     cae     eac     aec     cea     eca     acf     caf     fac     afc
cfa     fca     ade     dae     ead     aed     dea     eda     adf     daf
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

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


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

Comments and Discussions

 
GeneralI like this Pin
CalvinHobbies16-Nov-09 21:56
CalvinHobbies16-Nov-09 21:56 
GeneralRecursion Pin
PIEBALDconsult16-Nov-09 4:56
mvePIEBALDconsult16-Nov-09 4:56 
GeneralRe: Recursion Pin
Aviad P.16-Nov-09 6:42
Aviad P.16-Nov-09 6:42 
GeneralRe: Recursion Pin
PIEBALDconsult16-Nov-09 8:22
mvePIEBALDconsult16-Nov-09 8:22 
GeneralRe: Recursion Pin
Aviad P.16-Nov-09 9:17
Aviad P.16-Nov-09 9:17 
GeneralRe: Recursion [modified] Pin
mb1816-Nov-09 10:31
mb1816-Nov-09 10:31 
GeneralRe: Recursion Pin
Aviad P.17-Nov-09 4:09
Aviad P.17-Nov-09 4:09 
I'm currently working on an almost equally simple implementation of O(N) (N - is the size of the output, not the input in this case) time complexity using LinkedList. The LinkedList can be employed to provide such time complexity for permutations as well.

I am not sure if I should update my 2 articles or if I should post a new once, since the implementation is quite different.
GeneralRe: Recursion Pin
PIEBALDconsult16-Nov-09 14:38
mvePIEBALDconsult16-Nov-09 14:38 
GeneralRe: Recursion Pin
Lee N Middleton6-Dec-10 6:12
Lee N Middleton6-Dec-10 6:12 
GeneralRe: Recursion Pin
PIEBALDconsult6-Dec-10 14:08
mvePIEBALDconsult6-Dec-10 14:08 
GeneralRe: Recursion Pin
Lee N Middleton7-Dec-10 5:02
Lee N Middleton7-Dec-10 5:02 
GeneralRe: Recursion Pin
PIEBALDconsult7-Dec-10 18:13
mvePIEBALDconsult7-Dec-10 18:13 

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.