Comment Générer des Combinaisons d'Éléments d'une Liste<T>.NET 4.0

J'ai une question qui est similaire, mais pas identique, à la a répondu ici.

Je voudrais une fonction de générer tous les k-combinaisons d'éléments à partir d'une Liste de n éléments. Notez que je suis à la recherche de combinaisons, pas de permutations, et que nous avons besoin d'une solution pour des k (c'est à dire, le codage en dur des boucles est un non-non).

Je suis à la recherche d'une solution qui est un) élégant, et b) peut être codée dans VB10/.Net 4.0.

Cela signifie a) des solutions nécessitant LINQ sont ok, b) les personnes utilisant le C# "rendement" de la commande ne sont pas.

L'ordre de la combinaisons n'est pas important (c'est à dire, lexicographiques, Gray-code, qu'est-ce-avez-vous) et de l'élégance est favorisée par rapport à la performance, si les deux sont en conflit.

(En OCaml et C# solutions ici serait parfait, si elles pouvaient être codé dans VB10.)

OriginalL'auteur Michael Dorfman | 2009-07-13

  1. 6

    Code en C# qui produit de la liste des combinaisons des tableaux de k éléments:

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

    Initialiseur de Collection syntaxe utilisée ici est disponible dans visual basic 2010 (source).

    OriginalL'auteur Sergii Volchkov

  2. 1

    J'ai essayé de créer une énumération qui peut accomplir cette tâche en VB. C'est le résultat:

    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

    ...et vous pouvez utiliser mon code de cette façon:

    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

    Mon code donne des combinaisons d'une longueur spécifiée (3 dans mon exemple), même si, je viens de réaliser que vous souhaitez avoir des combinaisons de n'importe quelle longueur (je pense), mais c'est un bon début.

    OriginalL'auteur Meta-Knight

  3. 1

    Il n'est pas clair pour moi dans la forme que vous souhaitez à votre code visual basic pour retourner les combinaisons qu'il génère, mais pour simplifier, nous supposons une liste de listes. VB permet la récursivité, et une solution récursive est plus simple. Faire des combinaisons plutôt que de permutations peuvent être obtenues facilement, simplement en respectant l'ordre de la liste d'entrée.

    Ainsi, les combinaisons de K éléments d'une liste L qui N long:

    1. aucun, si K > N
    2. l'ensemble de la liste L, si K == N
    3. si K < N, alors l'union des deux bouquets: ceux qui contiennent le premier élément de L, et des combinaisons de K-1 N-1 éléments; de plus, les combinaisons de K des N-1 éléments.

    En pseudo-code (en utilisant, par exemple .la taille à donner une liste de longueur, [] comme une liste vide, .ajouter pour ajouter un élément à une liste .tête pour obtenir une liste du premier élément .la queue pour obtenir la liste de "tous les, mais les premiers éléments 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

    Ce pseudo-code peut être plus concis si vous assumez la plus flexible de la liste de manipulation de la syntaxe. Par exemple, en Python ("pseudo-code exécutable") à l'aide de "découpage" et "compréhension de liste" syntaxe:

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

    Si vous avez besoin de avec beaucoup de détails construire des listes par la répétition .ajouter, ou peut, de façon concise, les construire par liste de compréhension de la notation de syntaxe détail (comme c'est le choix de la tête et la queue vs liste de découpage de notation pour obtenir le premier élément de la liste vs le reste): le pseudo-code est destiné à exprimer exactement la même idée (qui est aussi la même idée exprimée en anglais dans la précédente liste numérotée). Vous pouvez mettre en œuvre l'idée dans une langue qui est capable de récursivité (et, bien sûr, un minimum d'opérations de liste!-).

    OriginalL'auteur Alex Martelli

  4. 1

    Mon twist, la prestation d'une liste triée, d'abord par la longueur puis en 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

    OriginalL'auteur TknoSpz

  5. 0

    Je peux vous proposons la solution suivante - pas encore parfait, pas rapide, et il suppose que l'entrée est un ensemble, donc ne contient pas les éléments en double. Je vais ajouter quelques explications plus tard.

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

    Il génère une séquence de type boolean motifs qui déterminent si un élément appartient à la combinaison actuelle de départ avec k fois vrai (1) à gauche et le reste tout faux (0).

     n = 5 k = 3 
11100 
11010 
10110 
01110 
11001 
10101 
01101 
10011 
01011 
00100

    Le motif suivant est généré comme suit. Assumer la tendance actuelle est la suivante.

    00011110000110.....

    De balayage de gauche à droite et passez tous les zéros (false).

    000|11110000110....

    Analyse sur le premier bloc de (vrai).

    0001111|0000110....

    Déplacer tout le sauté d'ailleurs la plus à droite à la gauche.

    1110001|0000110...

    Et enfin déplacer le plus à droite sauté un d'une position vers la droite.

    1110000|1000110...

    OriginalL'auteur Daniel Brückner