Cómo generar combinaciones de elementos de una lista <T> en .NET 4.0

Question

Tengo una pregunta que es similar, pero no idéntica, a la respondió uno here.

Me gustaría una función de generar toda la k -combinaciones de elementos de una lista de n elementos. Tenga en cuenta que estoy buscando combinaciones, no permutaciones, y que necesitamos una solución para variar k (es decir, codificar los bucles es un no-no).

Estoy buscando una solución que sea a) elegante, yb) se pueda codificar en VB10/.Net 4.0.

Esto significa que a) las soluciones que requieren LINQ son correctas, b) las que utilizan el comando C# "yield" no lo son.

El orden de las combinaciones no es importante (es decir, lexicográfico, código gris, qué-tienes-usted) y la elegancia se ve favorecida por el rendimiento, si los dos están en conflicto.

(Los OCaml y C# here soluciones sería perfecto, si podían ser codificados en VB10.)

Answer 1

Código en C# que produce la lista de combinaciones como matrices de k elementos:

sintaxis de inicializador

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; 
    } 
} 

Colección utilizado aquí se encuentra disponible en VB 2010 (source).

Answer 2

He intentado crear un enumerable que pueden realizar esta tarea en VB. Este es el resultado:

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 

... y se puede usar mi código de esta manera:

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 

Mi código da combinaciones de una longitud especificada (3 en mi ejemplo), sin embargo, me he dado cuenta que deseas tener combinaciones de cualquier longitud (creo), pero es un buen comienzo.

Answer 3

Puedo ofrecer la siguiente solución: aún no es perfecta, no es rápida, y supone que la entrada es un conjunto, por lo tanto, no contiene elementos duplicados. Voy a agregar alguna explicación más tarde.

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(); 
    } 
} 

Se genera una secuencia de patrones booleanos que determinan si un elemento pertenece a la combinación corriente de arranque con k veces verdadero (1) en el muy izquierdo y el resto todo falso (0).

 
    n = 5 k = 3 

    11100 
    11010 
    10110 
    01110 
    11001 
    10101 
    01101 
    10011 
    01011 
    00100 

El siguiente patrón se genera de la siguiente manera. Suponga que el patrón actual es el siguiente.

00011110000110..... 

Escanee de izquierda a derecha y omita todos los ceros (falso).

000|11110000110.... 

Escanear más lejos en el primer bloque de unos (verdadero).

0001111|0000110.... 

Mueva todos los salteados además de la derecha a la izquierda.

1110001|0000110... 

Y finalmente mueva el más a la derecha saltado uno a una posición.

1110000|1000110... 

Answer 4

No me queda claro en qué forma desea que su código de Visual Basic para volver las combinaciones que genera, pero por simplicidad vamos a suponer una lista de listas. VB permite la recursión, y una solución recursiva es la más simple. Se pueden obtener combinaciones fácilmente en lugar de permutaciones, simplemente respetando el orden de la lista de entrada.

Por lo tanto, las combinaciones de elementos de K fuera de una lista L que es N elementos larga son:

1. ninguno, si K> N
2. toda la lista L, si K == N
3. si K < N, entonces la unión de dos racimos: aquellos que contienen el primer artículo de L y cualquiera de las combinaciones de K-1 de los otros artículos N-1; Además, las combinaciones de K de los otros elementos N-1.

En pseudocódigo (utilizando, por ejemplo .size para dar la longitud de una lista, [] como una lista vacía, .Append para añadir un elemento a una lista, para obtener .head primer elemento de una lista, .tail llegar la lista de "todos menos los primeros elementos de" 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 

Este pseudocódigo se puede hacer más concisa si se asume la sintaxis lista manipulación más flexible. Por ejemplo, en Python ("pseudocódigo ejecutable") usando "rebanar" y "comprensión de lista" sintaxis:

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:]) 

Ya sea que necesite para construir listas informa extensamente por .Append repetida, o de forma concisa puede construirlos por la lista notación comprensión , es un detalle de sintaxis (como es la elección de la notación de corte en la cabeza y la cola frente a la lista para obtener el primer elemento de la lista frente al resto): el pseudocódigo pretende expresar exactamente la misma idea (que también es la misma idea expresada en Inglés en la lista numerada anterior). Puede implementar la idea en cualquier idioma que sea capaz de recursión (y, por supuesto, algunas operaciones de lista mínima! -).

Answer 5

Mi giro, la entrega de una lista ordenada, primero por la longitud - a continuación, por la alfa

Imports System.Collections.Generic 

Public Class LettersList 

    Public Function GetList(ByVal aString As String) As List(Of String) 
     Dim returnList As New List(Of String) 

     ' Start the recursive method 
     GetListofLetters(aString, returnList) 

     ' Sort the list, first by length, second by alpha 
     returnList.Sort(New ListSorter) 

     Return returnList 
    End Function 

    Private Sub GetListofLetters(ByVal aString As String, ByVal aList As List(Of String)) 
     ' Alphabetize the word, to make letter key 
     Dim tempString As String = Alphabetize(aString) 

     ' If the key isn't blank and the list doesn't already have the key, add it 
     If Not (String.IsNullOrEmpty(tempString)) AndAlso Not (aList.Contains(tempString)) Then 
      aList.Add(tempString) 
     End If 

     ' Tear off a letter then recursify it 
     For i As Integer = 0 To tempString.Length - 1 
      GetListofLetters(tempString.Remove(i, 1), aList) 
     Next 
    End Sub 

    Private Function Alphabetize(ByVal aString As String) As String 
     ' Turn into a CharArray and then sort it 
     Dim aCharArray As Char() = aString.ToCharArray() 
     Array.Sort(aCharArray) 
     Return New String(aCharArray) 
    End Function 

End Class 

Public Class ListSorter 
    Implements IComparer(Of String) 

    Public Function Compare(ByVal x As String, ByVal y As String) As Integer Implements System.Collections.Generic.IComparer(Of String).Compare 
     If x.Length = y.Length Then 
      Return String.Compare(x, y) 
     Else 
      Return (x.Length - y.Length) 
     End If 
    End Function 
End Class