Como gerar combinações de elementos de uma lista In .NET 4.0
-
12-09-2019 - |
Pergunta
Eu tenho uma pergunta semelhante, mas não idêntica, à que respondeu aqui.
Eu gostaria de uma função gerar todos os k-Combinações de elementos de uma lista de n elementos. Observe que estou procurando combinações, não permutações, e que precisamos de uma solução para variar k (ou seja, codificar os loops é um não-não).
Estou procurando uma solução que seja a) elegante e b) pode ser codificada no VB10/.NET 4.0.
Isso significa que a) soluções que exigem LINQ estão ok, b) aquelas que usam o comando C# "rendimento" não são.
A ordem das combinações não é importante (isto é, lexicográfica, código cinza, o que você tem) e a elegância é favorecida pelo desempenho, se os dois estiverem em conflito.
(As soluções OCAML e C# aqui Seria perfeito, se eles pudessem ser codificados no VB10.)
Solução
Código em C# que produz lista de combinações como matrizes de k Elementos:
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;
}
}
Sintaxe inicializadora de coleção usada aqui está disponível no VB 2010 (fonte).
Outras dicas
Tentei criar um enumerável que possa realizar essa tarefa no VB. Este é o 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
... e você pode usar meu código desta maneira:
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
Meu código fornece combinações de um comprimento especificado (3 no meu exemplo), porém, acabei de perceber que você deseja ter combinações de qualquer comprimento (eu acho), mas é um bom começo.
Não está claro para mim de que forma você deseja que seu código VB retorne as combinações que ele gera, mas, por simplicidade, vamos assumir uma lista de listas. O VB permite a recursão e uma solução recursiva é mais simples. Fazer combinações em vez de permutações pode ser obtido facilmente, simplesmente respeitando a ordem da lista de entrada.
Portanto, as combinações de K itens fora de uma lista L que são n itens de comprimento são:
- Nenhum, se k> n
- toda a lista l, se k == n
- Se k <n, então a união de dois cachos: aqueles que contêm o primeiro item de L e qualquer uma das combinações de K-1 dos outros itens N-1; Além disso, as combinações de K dos outros itens N-1.
No pseudocode (usando, por exemplo .size para dar o comprimento de uma lista, [] como uma lista vazia, .Ppende para adicionar um item a uma lista, .head para obter o primeiro item de uma lista, .ilty para obter a lista de "todos, exceto os primeiros "itens 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 pode ser mais conciso se você assumir uma sintaxe de manipulação de lista mais flexível. Por exemplo, em Python ("Pseudocode executável") usando a sintaxe "Slicing" e "List Compreension":
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 você precisa construir verbosamente listas por repetidas. Append ou pode construí -las concisamente por notação de compreensão da lista, é um detalhe de sintaxe (como é a escolha da notação de corte de cabeça e cauda versus listas para obter o primeiro item da lista versus o resto ): O pseudocódigo pretende expressar exatamente a mesma idéia (que também é a mesma idéia expressa em inglês na lista numerada anterior). Você pode implementar a idéia em qualquer idioma capaz de recursão (e, é claro, algumas operações mínimas da lista!-).
Minha reviravolta, entregando uma lista classificada, primeiro por comprimento - depois por 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
Eu posso oferecer a solução a seguir - ainda não é perfeita, não rápida e assume que a entrada é um conjunto, portanto, não contém itens duplicados. Vou adicionar alguma explicação mais 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();
}
}
Ele gera uma sequência de padrões booleanos que determinam se um elemento pertence à combinação atual começando com k
vezes verdadeiro (1) à esquerda e o restante tudo falso (0).
n = 5 k = 3 11100 11010 10110 01110 11001 10101 01101 10011 01011 00100
O próximo padrão é gerado da seguinte maneira. Suponha que o padrão atual seja o seguinte.
00011110000110.....
Digitalize da esquerda para a direita e pule todos os zeros (falsos).
000|11110000110....
Digitalize mais sobre o primeiro bloco de (verdadeiro).
0001111|0000110....
Mova todos os pulsos além do mais à direita de volta para a esquerda.
1110001|0000110...
E finalmente mova o mais à direita, pulou uma única posição para a direita.
1110000|1000110...