Come generare combinazioni di elementi di una lista <T> in .NET 4.0

Question

Ho una domanda che è simile, ma non identica, a quella che ha risposto here.

Vorrei una funzione di generare tutte le k -combinazioni di elementi da un elenco di n elementi. Nota che sto cercando combinazioni, non permutazioni, e che abbiamo bisogno di una soluzione per la variazione di k (ad esempio, la codifica a caldo dei loop è un no-no).

Sto cercando una soluzione che sia a) elegante, e b) può essere codificata in VB10/.Net 4.0.

Ciò significa che a) le soluzioni che richiedono LINQ sono ok, b) quelle che utilizzano il comando C# "rendimento" non lo sono.

L'ordine delle combinazioni non è importante (cioè lessicografico, codice Gray, what-have-you) e l'eleganza è preferita rispetto alla performance, se i due sono in conflitto.

(Le soluzioni # OCaml e C here sarebbe perfetto, se potessero essere codificati in VB10.)

Answer 1

codice in C# che produce elenco di combinazioni come array di k elementi:

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 sintassi di inizializzazione utilizzato qui è disponibile in VB 2010 (source).

Answer 2

Ho cercato di creare un enumerabile in grado di svolgere questo compito in VB. Questo è il risultato:

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 

... ed è possibile utilizzare il mio codice in questo modo:

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 

Il mio codice dà una combinazione di una lunghezza specificata (3 nel mio esempio), però, ho appena realizzato che desideri avere combinazioni di qualsiasi lunghezza (credo), ma è un buon inizio.

Answer 3

Posso offrire la seguente soluzione, non ancora perfetta, non veloce, e presuppone che l'input sia un set, quindi non contiene elementi duplicati. Aggiungerò qualche spiegazione in seguito.

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

Esso genera una sequenza di pattern booleane che determinano se un elemento appartiene alla combinazione corrente di avviamento con k volte true (1) per lo sinistro e il resto tutto falso (0).

 
    n = 5 k = 3 

    11100 
    11010 
    10110 
    01110 
    11001 
    10101 
    01101 
    10011 
    01011 
    00100 

Il modello successivo viene generato come segue. Supponiamo che il modello attuale sia il seguente.

00011110000110..... 

Scansione da sinistra a destra e saltare tutti gli zeri (falso).

000|11110000110.... 

Scan ulteriormente nel primo blocco di quelli (veri).

0001111|0000110.... 

Spostare tutti quelli saltati oltre quello più a destra all'estrema sinistra.

1110001|0000110... 

Infine spostare l'elemento più a destra saltato di una posizione singola verso destra.

1110000|1000110... 

Answer 4

Non è chiaro per me in quale forma si desidera che il codice VB per restituire le combinazioni che genera, ma per semplicità supponiamo una lista di liste. VB consente la ricorsione e una soluzione ricorsiva è la più semplice. Fare combinazioni piuttosto che permutazioni può essere ottenuto facilmente, semplicemente rispettando l'ordine della lista di input.

Così, le combinazioni di elementi K su una lista L che è N elementi lungo sono:

1. nessuno, se K> N
2. l'intera lista L, se K == N
3. se K < N, allora l'unione di due mazzi: quelli che contengono il primo elemento di L e una qualsiasi delle combinazioni di K-1 degli altri oggetti N-1; inoltre, le combinazioni di K degli altri oggetti N-1.

In pseudocodice (usando per esempio .size per dare la lunghezza di una lista, [] come una lista vuota, .Append per aggiungere un elemento a un elenco, .head per ottenere prima voce di un elenco, per ottenere .tail la lista di "tutti, ma i primi" oggetti di 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 

Questo pseudocodice può essere resa più concisa se si assume la sintassi lista-manipolazione più flessibile. Per esempio, in Python ("pseudocodice eseguibile") utilizzando "affettare" e "lista di comprensione" la sintassi:

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

Se avete bisogno di costruire verbosamente liste da ripetuti .Append, o possibile conciso li costruire da comprensione lista notazione , è un dettaglio della sintassi (come la scelta tra la testa e la coda e l'elenco delle notazioni di taglio per ottenere il primo elemento della lista rispetto al resto): lo pseudocodice ha lo scopo di esprimere esattamente la stessa idea (che è anche la stessa idea espressa in Inglese nella precedente lista numerata). È possibile implementare l'idea in qualsiasi linguaggio che sia in grado di ricorsione (e, ovviamente, alcune operazioni di lista minima! -).

Answer 5

mio tocco, offrendo un elenco ordinato, in primo luogo per lunghezza - quindi con 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