Skip to content

Combinations of IEnumerable<T>

by Alex Peck on November 25th, 2009

Today I needed to generate all the combinations of elements in a collection. After some fruitless searching I was forced to engage my brain, and came up with the following iterator block. I’m making no extravagant claims about performance (skip, take and count could all be faster).

/// <summary>
/// Compute the set of combinations, where a combination is an un-ordered collection 
/// of elements taken from the candidate set. Each element must appear zero or once. 
/// For set [1,2,3], the combinations are [1], [1,2], [1,2,3], [2], [2,3] and [3].
/// </summary>
/// <typeparam name="T">The type of objects whose combinations we evaluate</typeparam>
/// <param name="set">The set from which to combine elements</param>
/// <returns>The set of combinations</returns>
public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> set)
{
    int n = set.Count();
 
    for (int skip = 0; skip < n; skip++)
    {
        for (int take = 1; take <= n - skip; take++)
        {
            yield return set.Skip(skip).Take(take);
        }
    }
}

Just to prove it works, here are my tests.

[TestMethod]
public void CombinationsOfNone()
{
    var candidates = new List<int>();
    var combinations = new List<List<int>>();
 
    AssertEqualSetsOfSets(combinations, candidates.Combinations());
}
 
[TestMethod]
public void CombinationsOfOne()
{
    var candidates = new List<int>() { 1 };
 
    var combinations = new List<List<int>>() 
    { 
        new List<int>() {1}
    };
 
    AssertEqualSetsOfSets(combinations, candidates.Combinations());
}
 
[TestMethod]
public void CombinationsOfThree()
{
    var candidates = new List<int>() { 1, 2, 3 };
 
    var combinations = new List<List<int>>() 
    { 
        new List<int>() {1}, 
        new List<int>() {1, 2},
        new List<int>() {1, 2, 3},
        new List<int>() {2},
        new List<int>() {2, 3},
        new List<int>() {3}
    };
 
    AssertEqualSetsOfSets(combinations, candidates.Combinations());
}
 
private void AssertEqualSetsOfSets(List<List<int>> expected, IEnumerable<IEnumerable<int>> actual)
{
    Assert.AreEqual<int>(expected.Count, actual.Count());
 
    var expectedIter = expected.GetEnumerator();
    var actualIter = actual.GetEnumerator();
 
    while (expectedIter.MoveNext() && actualIter.MoveNext())
    {
        Assert.IsTrue(OrderIndependentEqual(expectedIter.Current, actualIter.Current));
    }
}
 
public bool OrderIndependentEqual<T>(IEnumerable<T> first, IEnumerable<T> second)
{
    return !first.Except(second).Concat(second.Except(first)).Any();
}
No comments yet

Leave a Reply

Note: XHTML is allowed. Your email address will never be published.

Subscribe to this comment feed via RSS