A C# Combinations Iterator

• Download source - 19.18 KB

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):

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