So Erzeugen Sie Kombinationen der Elemente einer List<T> in .NET 4.0
Ich habe eine Frage, die ist ähnlich, aber nicht identisch sind, auf die niemand geantwortet hier.
Ich würde gerne eine Funktion generieren, die alle k-Kombinationen von Elementen aus einer Liste von n Elementen. Beachten Sie, dass ich bin auf der Suche nach Kombinationen, nicht Permutationen, und wir brauchen eine Lösung für die unterschiedlichen k (D. H., die Feste Codierung der Schleifen ist ein no-no).
Ich bin auf der Suche nach einer Lösung, die a) elegant, und b) programmiert werden können, in VB10/.Net 4.0.
Dies bedeutet a) Lösungen, die LINQ ok sind, b) die Verwendung der C# "Ausbeute" - Befehl nicht.
Die Reihenfolge der Kombinationen ist nicht von Bedeutung (d.h., lexikographische, Gray-code, was-haben-Sie) und Eleganz ist wichtiger als Leistung, wenn die beiden in Konflikt.
(Die OCaml und C# - Lösungen hier wäre perfekt, wenn Sie könnten, werden codiert in VB10.)
Du musst angemeldet sein, um einen Kommentar abzugeben.
Code in C# erzeugt Liste von Kombinationen, die als arrays von k Elemente:
Collection-Initialisierer-syntax, die hier verwendet ist in VB 2010 (Quelle).
Habe ich versucht die Schaffung einer aufzählbaren kann diese Aufgabe in VB. Dies ist das Ergebnis:
...und Sie kann meinen code so:
Mein code gibt Kombinationen einer vorgegebenen Länge (3 in meinem Beispiel) obwohl, ich erkannte, dass Sie haben wollen-Kombinationen in beliebiger Länge (denke ich), aber es ist ein guter Anfang.
Es ist mir nicht klar, in welcher form Sie möchten, dass Ihre VB-code, um die Rückkehr der Kombinationen, die es erzeugt, aber der Einfachheit wegen nehmen wir an, eine Liste von Listen. VB erlaubt Rekursion und rekursive Lösung ist die einfachste. Dabei Kombinationen statt Permutationen können leicht erhalten werden, indem man einfach Respekt für die Reihenfolge der input-Liste.
So, der Kombinationen von K Elementen aus einer Liste L, der N Elemente lang sind:
In pseudocode (mit zum Beispiel .Größe zu geben, die Liste ist lang, [] eine leere Liste .fügen Sie zum hinzufügen eines Elements zu einer Liste .Kopf aus, um eine Liste das erste Element .Schwanz beim abrufen der Liste von "alle, aber die ersten" Elemente von L):
Dieser pseudocode gemacht werden kann, kurz, wenn Sie davon ausgehen, flexibler Liste-manipulation syntax. Zum Beispiel in Python ("ausführbarer pseudocode") mit "slicing" und "list comprehension" - syntax:
Ob Sie brauchen, um wortreich zu konstruieren Listen wiederholt .Anhängen, oder kann kurz und prägnant konstruieren Sie durch die Liste Verständnis notation, ist eine syntax-Details (wie ist die Wahl der head-und tail-vs-Liste slicing-notation, um das erste Element der Liste vs den rest): der pseudocode soll zum Ausdruck bringen, genau die gleiche Idee (die auch die gleiche Idee ausgedrückt in Englisch in der vorherigen nummerierte Liste). Können Sie die Idee umsetzen, in irgendeiner Sprache, die fähig ist, die Rekursion (und, natürlich, einige minimale Liste Operationen!-).
Mein twist, liefert eine sortierte Liste, indem Sie zuerst der Länge, dann durch alpha
Bieten kann ich folgende Lösung noch nicht perfekt, nicht schnell, und es nimmt die Eingabe aus einem set, daher enthält keine doppelten Elemente. Ich bin hinzufügen, einige Erklärungen später.
Es generiert eine Sequenz von booleschen Muster, die bestimmen, ob ein element gehört, um die aktuelle Kombination beginnend mit
k
mal true (1) ganz Links und der rest alle auf false (0).Wird das nächste Muster wird wie folgt generiert. Davon ausgehen, dass das aktuelle Muster ist die folgende.
Scan von Links nach rechts und überspringen alle Nullen (false).
Scannen weitere über dem ersten block von Einsen (wahr).
Verschieben Sie alle übersprungen diejenigen, die neben der rechten zurück auf die linke.
Und schließlich bewegen Sie den rechten übersprungen, mit einer einzigen position auf der rechten Seite.