Comment générer des combinaisons d'éléments d'une liste dans .NET 4.0

Question

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

Je voudrais une fonction de générer tous les k -ensembles des éléments d'une liste d'éléments n. Notez que je suis à la recherche des combinaisons, des permutations pas, et que nous avons besoin d'une solution pour faire varier k (à savoir coder en dur les boucles est un non-non).

Je cherche une solution qui est a) élégant et b) peuvent être écrites en langage VB10 / .Net 4.0.

Cela signifie a) des solutions nécessitant LINQ sont ok, b) ceux qui utilisent la commande C # "rendement" ne sont pas.

L'ordre des combinaisons est pas important (à savoir, lexicographique, code Gray, ce que vous voudrez) et de l'élégance est favorisée par rapport à la performance, si les deux sont en conflit.

(Le OCaml et solutions C # ici serait parfait, si elles peuvent être codées en VB10.)

Answer 1

code en C # qui produit la liste des combinaisons sous forme de 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;
    }
}

Collection syntaxe initialiseur utilisée ici est disponible en VB 2010 ( la source ).

Answer 2

J'ai essayé de créer un dénombrable qui peut accomplir cette tâche en VB. Ceci 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 durée déterminée (3 dans mon exemple), bien que, je viens de réaliser que vous souhaitez avoir des combinaisons de longueur quelconque (je pense), mais il est un bon début.

Answer 3

Il est pas clair pour moi sous quelle forme vous voulez que votre code VB pour renvoyer les combinaisons qu'elle génère, mais pour simplifier supposons une liste de listes. VB ne permet récursion, et une solution récursive est plus simple. Faire des combinaisons plutôt que sur des permutations peuvent être obtenus facilement, simplement en respectant l'ordre de la liste d'entrée.

Ainsi, les combinaisons d'éléments K sur une liste L qui est N éléments à long sont:

1. none, si K> N
2. toute la liste L, si K == N
3. si K

En pseudocode (en utilisant par exemple .Size pour donner la longueur d'une liste, [] comme une liste vide, .append pour ajouter un élément à une liste, .HEAD pour obtenir premier élément d'une liste, .tail pour obtenir la liste des "tout sauf 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

Cette pseudo-code peut être plus concis si vous assumez plus flexible la syntaxe liste de manipulation. Par exemple, en Python ( « exécutable de pseudo-code ») en utilisant « découpage » et la syntaxe « la compréhension de la liste »:

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

Que vous ayez besoin de construire verbeux listes par .append répétées, ou peut de façon concise les construire par la notation de la compréhension de la liste, est un détail de syntaxe (tout comme le choix de la tête et la queue vs notation de découpage en tranches de liste pour obtenir le premier élément de la liste vs le reste): le pseudo-code est destiné à exprimer la même idée (qui est aussi la même idée exprimée en anglais dans la liste numérotée précédente). Vous pouvez mettre en œuvre l'idée dans une langue qui est capable de récursion (et, bien sûr, certaines opérations de liste minimale -).

Answer 4

Ma torsion, fournissant une liste triée, d'abord par longueur - puis par 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

Answer 5

Je peux proposer la solution suivante - pas encore parfait, pas vite, et il suppose que l'entrée est un ensemble, ne contient donc aucun élément 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 motifs booléennes qui déterminent si un élément appartient à la combinaison de courant de démarrage avec des temps de k true (1) à l'extrême gauche et le reste tout faux (0).

  n = 5  k = 3

  11100
  11010
  10110
  01110
  11001
  10101
  01101
  10011
  01011
  00100

Le schéma suivant est généré de la manière suivante. Supposons que le motif courant est le suivant.

00011110000110.....

Numériser de gauche à droite et sauter tous les zéros (false).

000|11110000110....

Numérisation en outre sur le premier bloc de ceux (vrai).

0001111|0000110....

Déplacer tous ceux sautées en plus à l'extrême droite un retour à l'extrême gauche.

1110001|0000110...

Et enfin passer à l'extrême droite a sauté une position unique à droite.

1110000|1000110...