Kombinationen rekursiv ermitteln

  • VB.NET

Es gibt 6 Antworten in diesem Thema. Der letzte Beitrag () ist von Live.

    Kombinationen rekursiv ermitteln

    Hallo liebe VBParadise-Gemeinde! :)
    ich möchste mit folgendem Code rekursiv alle Kombinationsmöglichkeiten von den Items in der Übergebenen Liste ls bestimmen. Dh, wenn die liste die Items A, B, C, D enthält, soll zunächst per Messagebox ABCD, ABDC, ACBD, BCDA, ... angezeigt werden. Leider klappt das nicht so ganz :/
    Hier mein Code:

    VB.NET-Quellcode

    1. Sub Kombination_Rekursiv(ByVal ls As List(Of String), ByVal kombination As List(Of String))
    2. If ls.Count = 0 Then
    3. MsgBox(String.Join(" ", kombination.ToArray))
    4. Exit Sub
    5. End If
    6. For Each i As String In ls
    7. Dim nls As List(Of String) = ls
    8. nls.Remove(i)
    9. kombination.Add(i)
    10. Kombination_Rekursiv(nls, kombination)
    11. Next
    12. End Sub

    ls ist dabei wie gesagt immer die Liste mit den Items die Kombiniert werden sollen. Zunächst überprüfe ich, ob diese Liste leer ist, wenn ja, so sind alle Items in der Liste aufgebraucht und damit in der Liste kombination gespeichert und diese kann ausgegeben werden. Dann wird jedes Item der Liste durchgegangen und eine neue Liste nls erstellt, die das jeweilige Element nicht enthält, dafür aber kombination. Dann wird rekursiv der nächste Kombinationsvorgang aufgerufen (ich hoffe ich konnte meine Gedanken verständlich machen).
    Leider bricht die Prozedur immer mit folgender Fehlermeldung bei der Next-Anweisung ab:
    System.InvalidOperationException wurde nicht behandelt.
    Message="Die Auflistung wurde geändert. Der Enumerationsvorgang kann möglicherweise nicht ausgeführt werden."

    Aber es wurde die ls-Liste doch gar nicht geändert? oO
    Hoffe ihr könnt mir helfen. :) LG
    --- Zurzeit inaktiv ---

    Vielleicht probierst Du es erst mal mit 4 ineinander geschachtelten For-Schleifen.
    Die Ausgabe in einer MessageBox ist da wohl suboptimal, nimm eine TextBox.
    Falls Du diesen Code kopierst, achte auf die C&P-Bremse.
    Jede einzelne Zeile Deines Programms, die Du nicht explizit getestet hast, ist falsch :!:
    Ein guter .NET-Snippetkonverter (der ist verfügbar).
    Programmierfragen über PN / Konversation werden ignoriert!

    Hi! :)
    Ja, mit ineinander geschachtelten Schleifen funktionierts ja - bloss das Problem ist, dass die Anzahl der Items in der Liste variabel ist... deswegen ja auch die Rekursion.
    Okay, ich bin jetzt mal auf Controls zur Ausgabe umgestiegen ;) (leider immer noch die selbe Fehlermeldung....)
    --- Zurzeit inaktiv ---

    Rekursion brauchst du erst dann, wenn die Länge der Abfolge variabel ist (z.B. 5 statt 4 Stellen).
    Eigentlich müsstest du ja N for Schleifen ineinander schachteln. Dieses Problem lößt die Rekusion.
    Wenn du statt A-D A-E haben willst brauchst du noch keine Rekursion.

    €: Ich hab wahrscheinlich Blödsinn geschrieben. Ich habe mich nicht auf Permutation bezogen, sonder auf alle Möglichkeiten wie bei einem Zahlenschloss (mehrfache Verwendung eines Elements erlaubt).

    Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „markus.obi“ ()

    Hi
    ginge eigentlich sogar relativ einfach. Übergib einer Sub vier Parameter:
    - die zu permutierenden Elemente
    - ein BitArray, das die gleiche Anzahl an Elementen enthält, wie die zu permutierende Liste
    - die festen Elemente
    - das Ziel (Liste, Collection oder halt als Funktion und im Rückgabewert ein Enumerator)
    In einem Aufruf überpüfst du, ob die Länge der zu permutierernden Elemente gleich der Anzahl der festen Elemente ist. Sofern das zutrifft, fügst du eine Kopie der festen Elemente (oder halt in ein Array kopiert) in die Zielliste. Andernfalls gehst du alle Elemente durch und überprüfst, ob das Flag im Bit-Array gesetzt ist. Wenn es nicht gesetzt ist, setzt du es, fügst es zur Auflistung der festen Elemente hinzu und rufst die Methode auf sich selbst auf, setzt das Flag im Bit-Array anschließend wieder auf nicht gesetzt und entfernst das letzte Element der Auflistung mit den festen Elementen.
    Das Bit-Array dient dazu, dass du festhältst, welche Elemente bereits in der Permutation enthalten sind. Sonst müsstest du immer alle Elemente erst durchlaufen oder eine neue Liste pro Aufruf erzeugen, um die verbleibdenen Elemente festzuhalten. Performanter ist's aber, es einfach so zu lösen, da Kopieroperationen kostenspieliger sind, als Abfragen und setzen. Die festen Elemente stellen letztendlich die Permutation dar, wenn keine Elemente mehr verbleiben und somit eben die Anzahl der festen Elemente der Anzahl der permutierenden Elemente entspricht.

    Gruß
    ~blaze~

Facebook
Telefonspende