So generieren Sie Kombinationen von Elementen eines ListT in .NET 4.0

8

Ich habe eine ähnliche, aber nicht identische Frage an die Antwort hier.

Ich möchte, dass eine Funktion alle k -Kombinationen von Elementen aus einer Liste von n Elementen erzeugt. Beachten Sie, dass ich nach Kombinationen suche, nicht nach Permutationen, und dass wir eine Lösung für das Variieren von k benötigen (d. H., Das Schleifen der Schleifen ist ein Nein-Nein).

Ich suche nach einer Lösung, die a) elegant ist und b) in VB10 / .Net 4.0 codiert werden kann.

Dies bedeutet a) Lösungen, die LINQ erfordern, sind in Ordnung, b) diejenigen, die den C # "yield" -Befehl verwenden, sind dies nicht.

Die Reihenfolge der Kombinationen ist nicht wichtig (d. h. lexikographisch, Gray-Code, Was-Haben-Du), und Eleganz wird gegenüber Leistung bevorzugt, wenn die beiden Konflikte haben.

(Die OCaml- und C # -Lösungen hier wäre perfekt, wenn sie in VB10 codiert werden könnten.

    
Michael Dorfman 13.07.2009, 14:16
quelle

5 Antworten

6

Code in C #, der eine Liste von Kombinationen als Arrays von k Elementen erzeugt:

%Vor%

Die hier verwendete Sammlungsinitialisierungssyntax ist in VB 2010 ( Quelle ) verfügbar ).

    
Sergii Volchkov 20.07.2009, 00:13
quelle
1

Ich habe versucht, ein Enumerable zu erstellen, das diese Aufgabe in VB ausführen kann. Dies ist das Ergebnis:

%Vor%

... und Sie können meinen Code auf diese Weise verwenden:

%Vor%

Mein Code gibt Kombinationen einer bestimmten Länge (3 in meinem Beispiel), aber ich habe gerade festgestellt, dass Sie Kombinationen beliebiger Länge haben möchten (denke ich), aber es ist ein guter Anfang.

    
Meta-Knight 13.07.2009 20:41
quelle
1

Es ist mir nicht klar, in welcher Form Ihr VB-Code die von ihm erzeugten Kombinationen zurückgeben soll, aber nehmen wir zur Vereinfachung eine Liste von Listen an. VB erlaubt Rekursion, und eine rekursive Lösung ist am einfachsten. Das Ausführen von Kombinationen anstelle von Permutationen kann leicht erreicht werden, indem einfach die Reihenfolge der Eingabeliste respektiert wird.

Also sind die Kombinationen von K Elementen aus einer Liste L, die N Elemente lang sind:

  1. keine, wenn K & gt; N
  2. die ganze Liste L, wenn K == N
  3. falls K & lt; N, dann die Vereinigung von zwei Bündeln: diejenigen, die den ersten Gegenstand von L und irgendeine der Kombinationen von K-1 der anderen N-1 Gegenstände enthalten; Plus, die Kombinationen von K der anderen N-1 Elemente.

Im Pseudocode (z. B. .size, um die Länge einer Liste anzugeben, [] als leere Liste, .app, um ein Element zu einer Liste hinzuzufügen, .head, um das erste Element einer Liste zu erhalten, .tail um die Liste zu erhalten "alle außer den ersten" von L):

%Vor%

Dieser Pseudocode kann präziser gestaltet werden, wenn Sie eine flexiblere Listenmanipulationssyntax annehmen. Zum Beispiel in Python ("ausführbare Pseudocode") mit "Slicing" und "Liste Verständnis" -Syntax:

%Vor%

Ob Sie ausführlich Listen mit wiederholtem .append konstruieren müssen oder sie kompakt nach Listenverständnisnotation konstruieren können, ist ein Syntaxdetail (ebenso wie die Wahl von Kopf- und End- vs. Listen-Slicing-Notation, um das erste Element der Liste zu erhalten) vs. der Rest): Der Pseudocode soll genau dieselbe Idee ausdrücken (was auch die gleiche Idee ist, die in der vorherigen nummerierten Liste auf Englisch ausgedrückt wird). Sie können die Idee in jeder Sprache implementieren, die rekursiv ist (und natürlich einige minimale Listenoperationen! -).

    
Alex Martelli 18.07.2009 21:02
quelle
1

Mein Dreh, sortiere eine sortierte Liste zuerst nach Länge - dann nach Alpha

%Vor% %Vor%     
TknoSpz 15.03.2011 17:25
quelle
0

Ich kann die folgende Lösung anbieten - noch nicht perfekt, nicht schnell, und es nimmt an, dass die Eingabe eine Menge ist und daher keine doppelten Elemente enthält. Ich werde später eine Erklärung hinzufügen.

%Vor%

Er erzeugt eine Folge von booleschen Mustern, die bestimmen, ob ein Element zu der aktuellen Kombination gehört, beginnend mit k mal wahr (1) ganz links und der Rest alle falsch (0).

%Vor%

Das nächste Muster wird wie folgt generiert. Angenommen, das aktuelle Muster ist das folgende.

%Vor%

Scanne von links nach rechts und überspringe alle Nullen (false).

%Vor%

Scanne weiter über den ersten Block von Einsen (wahr).

%Vor%

Verschiebe alle übersprungenen außer dem rechten ganz nach links.

%Vor%

Und schließlich verschieben Sie den ganz rechts übersprungenen um eine Position nach rechts.

%Vor%     
Daniel Brückner 14.07.2009 17:33
quelle

Tags und Links

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Wo speicher ich zusätzliche Benutzerdetails mit ASP.NET MVC und dem SqlMembershipProvider?