# Combinations of IEnumerable<T>

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(); } |