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

I tried creating an enumerable that can accomplish this task in VB. This is the result:

Public Class CombinationEnumerable(Of T)
Implements IEnumerable(Of List(Of T))

Private m_Enumerator As CombinationEnumerator

Public Sub New(ByVal values As List(Of T), ByVal length As Integer)
    m_Enumerator = New CombinationEnumerator(values, length)
End Sub

Public Function GetEnumerator() As System.Collections.Generic.IEnumerator(Of List(Of T)) Implements System.Collections.Generic.IEnumerable(Of List(Of T)).GetEnumerator
    Return m_Enumerator
End Function

Private Function GetEnumerator1() As System.Collections.IEnumerator Implements System.Collections.IEnumerable.GetEnumerator
    Return m_Enumerator
End Function

Private Class CombinationEnumerator
    Implements IEnumerator(Of List(Of T))

    Private ReadOnly m_List As List(Of T)
    Private ReadOnly m_Length As Integer

    ''//The positions that form the current combination
    Private m_Positions As List(Of Integer)

    ''//The index in m_Positions that we are currently moving
    Private m_CurrentIndex As Integer

    Private m_Finished As Boolean


    Public Sub New(ByVal list As List(Of T), ByVal length As Integer)
        m_List = New List(Of T)(list)
        m_Length = length
    End Sub

    Public ReadOnly Property Current() As List(Of T) Implements System.Collections.Generic.IEnumerator(Of List(Of T)).Current
        Get
            If m_Finished Then
                Return Nothing
            End If
            Dim combination As New List(Of T)
            For Each position In m_Positions
                combination.Add(m_List(position))
            Next
            Return combination
        End Get
    End Property

    Private ReadOnly Property Current1() As Object Implements System.Collections.IEnumerator.Current
        Get
            Return Me.Current
        End Get
    End Property

    Public Function MoveNext() As Boolean Implements System.Collections.IEnumerator.MoveNext

        If m_Positions Is Nothing Then
            Reset()
            Return True
        End If

        While m_CurrentIndex > -1 AndAlso (Not IsFree(m_Positions(m_CurrentIndex) + 1)) _
            ''//Decrement index of the position we're moving
            m_CurrentIndex -= 1
        End While

        If m_CurrentIndex = -1 Then
            ''//We have finished
            m_Finished = True
            Return False
        End If
        ''//Increment the position of the last index that we can move
        m_Positions(m_CurrentIndex) += 1
        ''//Add next positions just after it
        Dim newPosition As Integer = m_Positions(m_CurrentIndex) + 1
        For i As Integer = m_CurrentIndex + 1 To m_Positions.Count - 1
            m_Positions(i) = newPosition
            newPosition += 1
        Next
        m_CurrentIndex = m_Positions.Count - 1
        Return True
    End Function

    Public Sub Reset() Implements System.Collections.IEnumerator.Reset
        m_Finished = False
        m_Positions = New List(Of Integer)
        For i As Integer = 0 To m_Length - 1
            m_Positions.Add(i)
        Next
        m_CurrentIndex = m_Length - 1
    End Sub

    Private Function IsFree(ByVal position As Integer) As Boolean
        If position < 0 OrElse position >= m_List.Count Then
            Return False
        End If
        Return Not m_Positions.Contains(position)
    End Function

    ''//Add IDisposable support here


End Class

End Class

...and you can use my code this way:

Dim list As New List(Of Integer)(...)
Dim iterator As New CombinationEnumerable(Of Integer)(list, 3)
    For Each combination In iterator
        Console.WriteLine(String.Join(", ", combination.Select(Function(el) el.ToString).ToArray))
    Next

My code gives combinations of a specified length (3 in my example) though, I just realized that you wish to have combinations of any length (I think), but it's a good start.

Answer 2

I can offer the following solution - not yet perfect, not fast, and it assumes the input is a set, hence contains no duplicate items. I am going to add some explanation later.

using System;
using System.Linq;
using System.Collections.Generic;

class Program
{
   static void Main()
   {
      Int32 n = 5;
      Int32 k = 3;

      Boolean[] falseTrue = new[] { false, true };

      Boolean[] pattern = Enumerable.Range(0, n).Select(i => i < k).ToArray();
      Int32[] items = Enumerable.Range(1, n).ToArray();

      do
      {
         Int32[] combination = items.Where((e, i) => pattern[i]).ToArray();

         String[] stringItems = combination.Select(e => e.ToString()).ToArray();
         Console.WriteLine(String.Join(" ", stringItems));

         var right = pattern.SkipWhile(f => !f).SkipWhile(f => f).Skip(1);
         var left = pattern.Take(n - right.Count() - 1).Reverse().Skip(1);

         pattern = left.Concat(falseTrue).Concat(right).ToArray();
      }
      while (pattern.Count(f => f) == k);

      Console.ReadLine();
   }
}

It generates a sequence of boolean patterns that determine if an element belongs to the current combination starting with k times true (1) at the very left and the rest all false (0).

  n = 5  k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

The next pattern is generated as follows. Assume the current pattern is the following.

00011110000110.....

Scan from left to right and skip all zeros (false).

000|11110000110....

Scan further over the first block of ones (true).

0001111|0000110....

Move all the skipped ones besides the rightmost one back to the very left.

1110001|0000110...

And finally move the rightmost skipped one a single position to the right.

1110000|1000110...

Answer 3

It's not clear to me in what form you want your VB code to return the combinations it generates, but for simplicity let's assume a list of lists. VB does allow recursion, and a recursive solution is simplest. Doing combinations rather than permutations can be obtained easily, by simply respecting the ordering of the input list.

So, the combinations of K items out of a list L that's N items long are:

1. none, if K > N
2. the whole list L, if K == N
3. if K < N, then the union of two bunches: those that contain the first item of L and any of the combinations of K-1 of the other N-1 items; plus, the combinations of K of the other N-1 items.

In pseudocode (using for example .size to give a list's length, [] as an empty list, .append to add an item to a list, .head to get a list's first item, .tail to get the list of "all but the first" items of L):

function combinations(K, L):
  if K > L.size: return []
  else if K == L.size: 
    result = []
    result.append L
    return result
  else:
    result = []
    for each sublist in combinations(K-1, L.tail):
      subresult = []
      subresult.append L.head
      for each item in sublist:
        subresult.append item
      result.append subresult
    for each sublist in combinations(K, L.tail):
      result.append sublist
    return result

This pseudocode can be made more concise if you assume more flexible list-manipulation syntax. For example, in Python ("executable pseudocode") using "slicing" and "list comprehension" syntax:

def combinations(K, L):
  if K > len(L): return []
  elif K == len(L): return [L]
  else: return [L[:1] + s for s in combinations(K-1, L[1:])
               ] + combinations(K, L[1:])

Whether you need to verbosely construct lists by repeated .append, or can concisely construct them by list comprehension notation, is a syntax detail (as is the choice of head and tail vs list slicing notation to get the first item of the list vs the rest): the pseudocode is intended to express exactly the same idea (which is also the same idea expressed in English in the previous numbered list). You can implement the idea in any language that is capable of recursion (and, of course, some minimal list operations!-).

Answer 4

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).