Come generare combinazioni di elementi di un List in .NET 4.0
-
12-09-2019 - |
Domanda
Ho una domanda che è simile, ma non identica, a quella che ha risposto qui.
Vorrei una funzione di generare tutte le k -complessi composti di elementi da un elenco di n elementi. Si noti che sto cercando combinazioni, non permutazioni, e che abbiamo bisogno di una soluzione per la variazione k (vale a dire, hard-codifica i loop è un no-no).
Sto cercando una soluzione che è a) elegante e b) può essere codificato in VB10 / .Net 4.0.
Questo significa a) che richiedono soluzioni LINQ sono ok, b) coloro che utilizzano il C # comando "resa" non lo sono.
L'ordine delle combinazioni non è importante (vale a dire, lessicografico, codice Gray, quello che-hanno-te) e l'eleganza è favorito rispetto alle prestazioni, se i due sono in conflitto.
(L'OCaml e C # soluzioni qui sarebbe perfetto, se potessero essere codificati in VB10.)
Soluzione
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;
}
}
sintassi Collezione initializer usata qui è disponibile in VB 2010 ( fonte ).
Altri suggerimenti
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 solo capito che si desidera avere le combinazioni di qualsiasi lunghezza (credo), ma è un buon inizio.
Non è chiaro per me in quale forma si desidera che il codice VB per restituire le combinazioni che genera, ma per semplicità supponiamo che una lista di liste. VB non consentire la ricorsione, e una soluzione ricorsiva è più semplice. Combinazioni fare piuttosto che permutazioni possono essere ottenuti facilmente, semplicemente rispettando l'ordine della lista in ingresso.
Quindi, le combinazioni di elementi K su una lista L che è N elementi lungo sono:
- nessuno, se K> N
- la lista intera L, se K == N
- se K
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, .tail per ottenere l'elenco dei "tutti, ma i primi" elementi 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" 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 notazione di lista, è un dettaglio la sintassi (come è la scelta di testa e la coda contro la notazione lista affettare per ottenere il primo elemento della lista vs il resto): il pseudocodice è destinato ad esprimere esattamente la stessa idea (che è anche la stessa idea espressa in inglese nella lista numerata precedente). È possibile implementare l'idea in qualsiasi lingua che è in grado di ricorsione (e, ovviamente, alcune operazioni elenco minimo -!).
Il mio tocco, offrendo un elenco ordinato, in primo luogo per lunghezza - quindi con alpha
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
posso offrire la seguente soluzione - non ancora perfetta, non veloce, e si assume l'ingresso è un insieme, contiene quindi nessun elementi duplicati. Ho intenzione di aggiungere 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 tempi k
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 è generato come segue. Si supponga che il modello attuale è la seguente.
00011110000110.....
Scansione da sinistra a destra e saltare tutti zero (falso).
000|11110000110....
Scansione ulteriormente nel primo blocco di quelli (true).
0001111|0000110....
Sposta tutti quelli saltati oltre a quello più a destra di nuovo alla stessa sinistra.
1110001|0000110...
E infine spostare il più a destra saltato uno un'unica posizione verso destra.
1110000|1000110...