How to use LINQ to find all combinations of n items from a set of numbers?

Question

I'm trying to write an algorithm to select all combinations of n values from a set of numbers. For instance, given the set: `1, 2, 3, 7, 8, 9` All combinations of 2 values from the set is: > (1, 2), (1, 3), (1, 7), (1, 8), (1, 9), (2, 3), (2, 7), (2, 8), (2, 9), (3, 7), (3, 8), (3, 9), (7, 8), (7, 9), (8, 9) And 3 is: > (1, 2, 3), (1, 2, 7), (1, 2, 8), (1, 2, 9), (1, 3, 7), (1, 3, 8), (1, 3, 9), (1, 7, 8), (1, 7, 9), (1, 8, 9), (2, 3, 7), (2, 3, 8), (2, 3, 9), (2, 7, 8), (2, 7, 9), (2, 8, 9), (3, 7, 8), (3, 7, 9), (3, 8, 9), (7, 8, 9) etc! I'm currently using methods to to yield return sets of combinations of 2, 3 and 4 values, but it seems to me this could be generalised in a LINQ query. Thanks for your help!

Answer 1

I think recursion can get a bit confusing but the main thing here is knowing how to use Select and SelectMany:

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IEnumerable<T> source, int size)

{

if (source == null) throw new ArgumentNullException(nameof(source));

if (size < 0) throw new ArgumentOutOfRangeException(nameof(size), "Size must be non-negative.");

if (size == 0) return new[] { Enumerable.Empty<T>() };

return source.SelectMany((element, index) =>

source.Skip(index + 1)

.Combinations(size - 1)

.Select(smallerCombination => new[] { element }.Concat(smallerCombination)));

}

Usage:

var numbers = new[] { 1, 2, 3, 7, 8, 9 };

foreach (var combination in numbers.Combinations(3))

Console.WriteLine("(" + string.Join(", ", combination) + ")");

However, if your are index visited tracking and just looping you can avoid a bunch of allocations for so you might be better off avoiding LINQ if things get really large.