How to Generate Combinations of Elements of a List<T> in .NET 4.0

Question

I have a question that is similar, but not identical, to the one answered here.

I would like a function generate all of the k-combinations of elements from a List of n elements. Note that I am looking for combinations, not permutations, and that we need a solution for varying k (i.e., hard-coding the loops is a no-no).

I am looking for a solution that is a) elegant, and b) can be coded in VB10/.Net 4.0.

This means a) solutions requiring LINQ are ok, b) those using the C# "yield" command are not.

The order of the combinations is not important (i.e., lexicographical, Gray-code, what-have-you) and elegance is favored over performance, if the two are in conflict.

(The OCaml and C# solutions here would be perfect, if they could be coded in VB10.)

Answer 1

Code in C# that produces list of combinations as arrays of k elements:

public static class ListExtensions
{
    public static IEnumerable<T[]> Combinations<T>(this IEnumerable<T> elements, int k)
    {
        List<T[]> result = new List<T[]>();

        if (k == 0)
        {
            // single combination: empty set
            result.Add(new T[0]);
        }
        else
        {
            int current = 1;
            foreach (T element in elements)
            {
                // combine each element with (k - 1)-combinations of subsequent elements
                result.AddRange(elements
                    .Skip(current++)
                    .Combinations(k - 1)
                    .Select(combination => (new T[] { element }).Concat(combination).ToArray())
                    );
            }
        }

        return result;
    }
}

Collection initializer syntax used here is available in VB 2010 (source).