Tip Enumerable(Of T) extension to get combinations

[JohnH]

For some project I needed to process a given number of combinations of items, for example all combinations of three items from a longer list. Instead of hardcoding loops (and one method for each additional combination level) or attempting my own recursion I searched web and found this short method using Enumerable extensions and recursion that happened to solve that quickly. FYI this allows a single iteration for any given combination count, thus a single method solution. The code I found was written in C# and there was some problems converting it since I could not first see where VB was complaining (it was mainly suggesting problems inferring parameter types). After some attempts there it was and I thought sharing this neat extension method, so here it is:

Imports System.Runtime.CompilerServices

Module Extensions

    <Extension()> Public Function Combinations(Of T)(ByVal elements As IEnumerable(Of T), ByVal k As Integer) As IEnumerable(Of IEnumerable(Of T))
        Return If(k = 0, {New T(-1) {}}, elements.SelectMany(Function(e, i) elements.Skip(i + 1).Combinations(k - 1).Select(Function(c) (New T() {e}).Concat(c))))
    End Function

End Module

With generics and the given type list you can see how this quickly gets complicated without inferring
Note: This works only for VB 2010, it ~didn't work~ in VB 2008.
Original code was found posted in thread: Algorithm to return all combinations of k elements from n - Stack Overflow

The actual return is IEnumerable(Of IEnumerable(Of T)), which means first level of return is all combination 'groups' and next level is the item combination. In the below practical example first level is each line, and second level is the three items.

Here is a sample output, to easier see what it does, imagine item list {A,B,C,D} and you want all combinations of three elements; items.Combinations(3):

A, B, C
A, B, D
A, C, D
B, C, D

According to this article Permutations, Combinations, and Variations using C# Generics - CodeProject this is called "combinations without repetitions" (ie AB equals BA, so no 'variations').

I can't exactly recall when, but I'm sure I have encountered uses for this several times before this round. Anyway, it is also an interesting study with all those Enumerable calls, think about what they do also in relation being recursive

 

[MattP]

Excellent work JohnH!

-----

Decided I'd try my hand at Permutations to go along with your Combinations method.

    <Extension()>
    Public Function Permutations(Of T)(ByVal elements As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))
        Return If(elements.Count() = 1,
                  {New T(-1) {}},
                  elements _
                        .Select(Function(e1, i1) Permutations(elements _
                        .Where(Function(e2, i2) i2 <> i1)) _
                        .Select(Function(e2) New List(Of T)() From {e1}.Union(e2))) _
                            .SelectMany(Function(c) c))
    End Function

And one using RX:

    <Extension()>
    Public Function PermutationsRX(Of T)(ByVal elements As IEnumerable(Of T)) As IEnumerable(Of IEnumerable(Of T))
        Return If(Not elements.Any(),
                  EnumerableEx.Return(Enumerable.Empty(Of T)()),
                  From e In Permutations(elements.Skip(1))
                  From i In Enumerable.Range(0, e.Count() + 1)
                  Select e.Take(i).Concat(EnumerableEx.Return(elements.First())).Concat(e.Skip(i)))
    End Function

 

[JohnH]

Perhaps you translated it from here Permutations with LINQ ? In that case the translation is not entirely correct, it does not give correct results, and I'm also not sure if its a good idea to mix the List(Of T) into this as it will cause the IEnumerable to be iterated (when "From {e1}.Union(e2)" that is). What's the mixup exactly I'm not sure, since it shouldn't really matter if that union was created from array or list, or list created from union'ed items. Though adding these parathesis will translate that code completely and give correct results:

[B][U]([/U][/B]New List(Of T)() From {e1}[B][U])[/U][/B].Union(e2)

New List(Of T)() From {e1} can instead be expressed as IEnumerable: New T() {e1}.
Using 'e2' as function parameter name in two different functions may be confusing, especially since one refer to a T element and the other to a IEnumerable(Of T) list, in above expression e2 is the latter.
For example new expression:

elements _
            .Select(Function(e, i) Permutations(elements.Where(Function(e2, i2) i2 <> i)) _
                                   .Select(Function(en) (New T() {e}).Union(en)) _
            ).SelectMany(Function(c) c)

I have not tried the RX yet.

 

[MattP]

You're absolutely correct on the issues with the first function and the lax naming conventions.

The second function has an error from me manually renaming it in the boards here.

From e In Permutations(elements.Skip(1))

Should Read:

From e In PermutationsRX(elements.Skip(1))

With that change you'll get the desired results

        Dim theList As New List(Of Integer) From {1, 2, 3, 4, 5}
        Dim perms = theList.PermutationsRX()