Generate number sequences with LINQ

Question

I try to write a LINQ statement which returns me all possible combinations of numbers (I need this for a test and I was inspired by this article of Eric Lippert). The method's prototype I call looks like:

IEnumerable<Collection<int>> AllSequences( int start, int end, int size );

The rules are:

• all returned collections have a length of size
• number values within a collection have to increase
• every number between start and end should be used

So calling the AllSequences( 1, 5, 3 ) should result in 10 collections, each of size 3:

1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4 
2 3 5
2 4 5 
3 4 5

Now, somehow I'd really like to see a pure LINQ solution. I am able to write a non LINQ solution on my own, so please put no effort into a solution without LINQ.
My tries so far ended at a point where I have to join a number with the result of a recursive call of my method - something like:

return from i in Enumerable.Range( start, end - size + 1 )
       select BuildCollection(i, AllSequences( i, end, size -1));

But I can't manage it to implement BuildCollection() on a LINQ base - or even skip this method call. Can you help me here?

Answer 1

Something like the following should do the job, I think.

public static IEnumerable<IEnumerable<int>> AllSequences(int start, int end,
    int size)
{
    return size <= 0 ? new[] { new int[0] } :
           from i in Enumerable.Range(start, end - size - start + 2)
           from seq in AllSequences(i + 1, end, size - 1)
           select Enumerable.Concat(new[] { i }, seq);
}

The key to the solution is the compound from clause, which is quite handy for dealing with nested enumerables.

Notice that I've changed the method signature slightly to IEnumerable<IEnumerable<int>>, since this is more convenient when using (pure) LINQ. You can always convert it easily to a IEnumerable<ICollection<int>> at the end if you like, however.

Let me know if the code needs any explanation, but I'm hoping the LINQ syntax makes it reasonably clear.

Edit 1: Fixed bug and improved conciseness.

Edit 2: Because I'm bored and have nothing better to do (no, not really), I thought I'd write an extension method that compute the combinations of a given list of elements, making use of the AllSequences method.

public static IEnumerable<IEnumerable<T>> Combinations<T>(this IList<T> source,
    int num)
{
    return AllSequences(0, source.Count - 1, num).Select(
        seq => seq.Select(i => source[i]));
}

Perhaps not the most efficient way of computing combinations, but certainly pretty compact code!

Answer 2

Think I've got it.

IEnumerable<List<int>> AllSequences(int start, int end, int size)
{
    if (size == 0)
        return Enumerable.Repeat<List<int>>(new List<int>(), 1);

    return from i in Enumerable.Range(start, end - size - start + 2)
           from seq in AllSequences(i + 1, end, size - 1)
           select new List<int>{i}.Concat(seq).ToList();
}