Permutation ohne Rekursion

    • VB.NET

    Es gibt 17 Antworten in diesem Thema. Der letzte Beitrag () ist von ThePlexian.

      Permutation ohne Rekursion

      Hallo mal wieder.

      Mir war gerade langweilig und deshalb habe ich mich an einem Permutationsalgorithmus versucht.
      Für alle, die nicht wissen, was Permutation ist: das ist die korrekte Bezeichnung für das Suchen aller möglichen Kombinationen aus einem gegebenen Satz Daten. Die Anzahl aller Permutationen berechnet sich nach der Fakultät der Mächtigkeit der Menge n = |Ω|!.
      Bsp.: alle Permutationen aus der Menge { 1, 2, 3 } sind

      Quellcode

      1. { 1, 2, 3 }
      2. { 1, 3, 2 }
      3. { 2, 1, 3 }
      4. { 2, 3, 1 }
      5. { 3, 1, 2 }
      6. { 3, 2, 1 }


      Um so etwas per Code zu realisieren bietet sich zunächst ein rekursiver Algorithmus an, da der Programmablauf dann klarer wird.

      VB

      VB.NET-Quellcode

      1. Public Shared Sub PermutateRecursive(chars As IEnumerable(Of Char), ByRef result As List(Of String))
      2. If chars.Count() = 1 Then
      3. result.Add(chars.First().ToString())
      4. Return
      5. End If
      6. For Each c In chars
      7. Dim buffer = New List(Of String)()
      8. PermutateRecursive(chars.Except({c}), buffer)
      9. For Each s In buffer
      10. result.Add(c & s)
      11. Next
      12. Next
      13. End Sub

      C#

      C-Quellcode

      1. public static void PermutateRecursive(IEnumerable<char> chars, ref List<string> result)
      2. {
      3. if (chars.Count() == 1)
      4. {
      5. result.Add(chars.First().ToString());
      6. return;
      7. }
      8. foreach (var c in chars)
      9. {
      10. var buffer = new List<string>();
      11. PermutateRecursive(chars.Except(new[] { c }), ref buffer);
      12. foreach (var s in buffer)
      13. result.Add(c + s);
      14. }
      15. }

      Dieser Code macht folgendes:
      chars ist die Menge, die permutiert werden soll.
      result sind alle Kombinationen, die aus der Menge gebildet werden können.
      Wenn die Mächtigkeit der Menge 1 beträgt, dann existiert nur genau eine Kombination. Diese kann sofort zurückgegeben werden.
      Ansonsten werden zunächst alle Kombinationen der um 1 reduzierten Menge gebildet, durch einen Rekursiven Aufruf an die Funktion. Diese gefundenen Kombinationen werden nun mit noch einer Schleife mit allen Elementen, die weggenommen wurden, kombiniert. Diese Kette setzt sich eben so lange fort, bis die Mächtigkeit der Teilmenge nur noch 1 beträgt.

      Dieser Code hat allerdings einige Nachteile. Zunächst einmal ist er rekursiv, was man in einem Programm nicht so gerne sieht, da dadurch der Stack ordentlich belegt wird. Weiterhin ist er langsam und verbraucht viel Speicher. Und zu guter letzt sind die Parameter auch nicht besonders schön zu verwenden. Es musste also was besseres her.


      Um zu verstehen, wie Permutation ohne Rekursion funktioniert, habe ich die Aufgabe zunächst etwas vereinfacht, indem ich lediglich einen Bruteforce-Algorithmus geschrieben habe. Bruteforce ist Permutation sehr ähnlich, allerdings dürfen die Elemente der Menge beliebig oft vorkommen. Damit errechnet sich die Anzahl aller möglichen Kombinationen nach n = |Ω|^i, wobei i die gewünschte Länge der Ausgabe ist.
      Bsp.: alle möglichen Kombinationen unter Verwendung von Bruteforce der Menge { 1, 2 } sind

      Quellcode

      1. { 1, 1 }
      2. { 1, 2 }
      3. { 2, 1 }
      4. { 2, 2 }


      Der Algorithmus dazu sieht so aus:

      VB

      VB.NET-Quellcode

      1. Public Shared Function Bruteforce(chars As Char(), count As Integer, includeSubLists As Boolean) As String()
      2. If count < 1 Then Return New String(-1) {}
      3. Dim buffer As String()
      4. Dim oldBuffer = {String.Empty}
      5. Dim result = New List(Of String)()
      6. While count > 0
      7. count -= 1
      8. buffer = New String(oldBuffer.Length * chars.Length - 1) {}
      9. Dim index = 0
      10. For i = 0 To oldBuffer.Length - 1
      11. For j = 0 To chars.Length - 1
      12. buffer(index) = oldBuffer(i) & chars(j)
      13. index += 1
      14. Next
      15. Next
      16. oldBuffer = buffer
      17. If includeSubLists OrElse count = 0 Then result.AddRange(buffer)
      18. End While
      19. Return result.ToArray()
      20. End Function

      C#

      C-Quellcode

      1. public static string[] Bruteforce(char[] chars, int count, bool includeSubLists)
      2. {
      3. if (count < 1)
      4. return new string[0];
      5. string[] buffer;
      6. var oldBuffer = new[] { string.Empty };
      7. var result = new List<string>();
      8. while (count > 0)
      9. {
      10. count--;
      11. buffer = new string[oldBuffer.Length * chars.Length];
      12. int index = 0;
      13. for (int i = 0; i < oldBuffer.Length; i++)
      14. for (int j = 0; j < chars.Length; j++, index++)
      15. buffer[index] = oldBuffer[i] + chars[j];
      16. oldBuffer = buffer;
      17. if (includeSubLists || count == 0)
      18. result.AddRange(buffer);
      19. }
      20. return result.ToArray();
      21. }

      Dieser Code ist nun schon etwas komplizierter. Hier die Erklärung:
      chars sind wieder die Eingabemenge.
      count ist die für die Ausgabe gewünschte Länge.
      includeSubLists gibt an, ob auch alle gefundenen Kombinationen von kleinerer Länge ausgegeben werden sollen.
      Zunächst wird überprüft, ob die Mächtigkeit der Menge größer 0 ist, wenn nicht, so existieren auch keine Kombinationen.
      Dann werden Arrays und Listen für den aktuellen Fortschritt, den Stand aus der vorherigen Iteration und für die Ausgabe angelegt. oldBuffer muss hierbei ein leeres Element enthalten, damit die erste Iteration funktioniert.
      Die while-Schleife geht nun alle Stellen der gewünschten Ausgabe durch. Zuerst wird der buffer angelegt, der alle Ergebnisse für diese Stelle speichern wird. Dann werden alle Ergebnisse aus der vorherigen Iteration mit allen Chars kombiniert und in den buffer geschrieben. Nun wird der aktuelle buffer zum alten buffer. Als letztes wird noch geprüft, ob etwas zur Ausgabe hinzugefügt werden muss. Dies ist der Fall, wenn etweder die aktuelle die letzte Iteration ist oder includeSubLists true ist.


      Auf diesem Code können wir nun aufbauen, um unser eigentliches Ziel zu erreichen. Beachten müssen wir hierbei aber, dass bei der Permutation count fest durch die Mächtigkeit der Menge festgelegt ist und includeSubLists nicht existieren kann. Dies vereinfacht und sie Arbeit aber auch auf eine gewisse Weise.
      Hier ist erstmal der fertige Algorithmus:

      VB

      VB.NET-Quellcode

      1. Public Shared Function Permutate(chars As Char()) As String()
      2. Dim buffer As String() = Nothing
      3. Dim oldBuffer = {String.Empty}
      4. For count = 0 To chars.Length - 1
      5. buffer = New String(If(buffer IsNot Nothing, buffer.Length, 1) * (chars.Length - count) - 1) {}
      6. Dim index = 0
      7. For i = 0 To oldBuffer.Length - 1
      8. For j = 0 To chars.Length - 1
      9. If Not oldBuffer(i).Contains(chars(j)) Then
      10. buffer(index) = oldBuffer(i) & chars(j)
      11. index += 1
      12. End If
      13. Next
      14. Next
      15. oldBuffer = buffer
      16. Next
      17. Return buffer
      18. End Function

      C#

      C-Quellcode

      1. public static string[] Permutate(char[] chars)
      2. {
      3. string[] buffer = null;
      4. var oldBuffer = new[] { string.Empty };
      5. for (int count = 0; count < chars.Length; count++)
      6. {
      7. buffer = new string[(buffer != null ? buffer.Length : 1) * (chars.Length - count)];
      8. int index = 0;
      9. for (int i = 0; i < oldBuffer.Length; i++)
      10. for (int j = 0; j < chars.Length; j++)
      11. if (!oldBuffer[i].Contains(chars[j]))
      12. {
      13. buffer[index] = oldBuffer[i] + chars[j];
      14. index++;
      15. }
      16. oldBuffer = buffer;
      17. }
      18. return buffer;
      19. }

      Erklärung:
      chars ist hier wieder die Eingabemenge.
      Wir legen uns wieder die buffer an, die zusätzliche Liste ist aber aufgrund eines nicht Vorhandenseins von includeSubLists nicht erforderlich, wir können später einfach den buffer zurückgeben.
      Wie ich bereits sagte wird count durch die Mächtigkeit der Menge festgelegt, weshalb wir die while-Schleife durch eine for-Schleife ersetzen können.
      Der buffer wird diesmal etwas anders initialisiert, da die Formel für die Anzahl der Ausgaben eine andere ist. Anstatt immer mit der kompletten Mächtigkeit zu multiplizieren multiplizieren wir mit der um n Elemente reduzierten Mächtigkeit, je nach dem wie viele Stellen wir bereits gebildet haben. So berechnen wir nach und nach nicht mehr die Potenz, sonder die Fakultät der Mächtigkeit der Eingabemenge.
      Die darauf folgenden Schleifen funktionieren genauso, wie vorher, jedoch werden diesmal die schon verwendeten Elemente ausgelassen.

      Ich hoffe ich konnte euch hier sowohl die Theorie als auch die Praxis etwas näher bringen. Wenn ihr noch fragen habt, nur her damit. Die Codes stammen übrigens vollständig von mir, also nichts aus dem Internet kopiert oder abgeschrieben, nicht mal die Theorie.

      Wichtige Anmerkung: ich will hier keine Anleitung zum Knacken von Passwörtern erstellen! Der obige Code ist dafür nicht vorgesehen und ich werde auch keine Erklärungen diesbezüglich bringen!
      Die Funktion hat sich gut als Extension für IEnumerable angeboten. Deshalb hab ich das jetzt auch mal umgesetzt.

      VB

      VB.NET-Quellcode

      1. <Extension>
      2. Public Shared Function Permutate(Of T)(value As IEnumerable(Of T)) As IEnumerable(Of List(Of T))
      3. Dim inputCount = value.Count()
      4. Dim buffer As List(Of T)() = Nothing
      5. Dim oldBuffer = New List(Of T)(inputCount - 1) {}
      6. For i = 0 To inputCount - 1
      7. oldBuffer(i) = New List(Of T)({value.ElementAt(i)})
      8. Next
      9. Dim bufferCount = inputCount
      10. For count = 1 To inputCount - 1
      11. buffer = New List(Of T)(bufferCount * (inputCount - count) - 1) {}
      12. Dim index = 0
      13. For i = 0 To oldBuffer.Length - 1
      14. For Each item In value
      15. If Not oldBuffer(i).Contains(item) Then
      16. Dim l = New List(Of T)(oldBuffer(i))
      17. l.Add(item)
      18. buffer(index) = l
      19. index += 1
      20. End If
      21. Next
      22. Next
      23. oldBuffer = buffer
      24. bufferCount = oldBuffer.Count()
      25. Next
      26. Return buffer
      27. End Function

      C#

      C-Quellcode

      1. public static IEnumerable<List<T>> Permutate<T>(this IEnumerable<T> value)
      2. {
      3. var inputCount = value.Count();
      4. List<T>[] buffer = null;
      5. var oldBuffer = new List<T>[inputCount];
      6. for (int i = 0; i < inputCount; i++)
      7. oldBuffer[i] = new List<T>(new[] { value.ElementAt(i) });
      8. var bufferCount = inputCount;
      9. for (int count = 1; count < inputCount; count++)
      10. {
      11. buffer = new List<T>[bufferCount * (inputCount - count)];
      12. int index = 0;
      13. for (int i = 0; i < oldBuffer.Length; i++)
      14. foreach (var item in value)
      15. if (!oldBuffer[i].Contains(item))
      16. {
      17. var l = new List<T>(oldBuffer[i]);
      18. l.Add(item);
      19. buffer[index] = l;
      20. index++;
      21. }
      22. oldBuffer = buffer;
      23. bufferCount = oldBuffer.Count();
      24. }
      25. return buffer;
      26. }

      Der RückgabeTyp ist hierbei leider nicht mehr so schön, wie bei der Char-Variante. Das liegt daran, dass ein String eine Auflistung von Chars ist. Solche Auflistungen gibts es für beliebige Typen aber nicht, weshalb es eine List(Of T) sein muss. Daher kommt dann das Verschachtelte IEnumerable.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „Artentus“ ()

      Artentus schrieb:

      Der RückgabeTyp ist hierbei leider nicht mehr so schön
      Was ist mit dem Rückgabetyp? Ich find den ganz schön.
      Der zeigt schön auf, dass eine Permutation nicht einfach eine Auflistung ist, sondern es ist eine (meist große) Auflistung von (meist kleinen) Auflistungen.

      Was du allerdings machen könntest, wäre IEnumerable(Of List(Of T)) zurückgeben, wo du eh intern mit List(Of T) arbeitest. Weil auch der "Abnehmer" kann wohl besser mit vielen List(of T) weitermachen.
      Ich dachte mir halt, dass bei einer Extension für IEnumerable auch wieder IEnumerables rauskommen sollten.
      Wenn man aber mit der List(OF T) arbeiten möchte, dann kann man das natürlich genauso gut machen, ist ja nur eine Kleinigkeit.

      Und klar zeigt der Rückgabetyp schöner, was eine Permutation eigentlich macht, ich meinte das auch eher im Sinne der Benutzbarkeit, da ein String-Array doch etwas handlicher als ein IEnumerable(OF IEnumerable)
      Erstmal danke für den Super Beitrag, verwende den Code zurzeit in einem kleinen Programm, hierbei ist mir aber aufgefallen, dass der Code ab 10-stelligen eingabewerten leider nicht mehr funktioniert. Der Debugger haut in der Zeile

      VB.NET-Quellcode

      1. If Not oldBuffer(i).Contains(chars(j)) Then​
      eine NullReferenceException raus.
      Ich vermute mal dass eine der verwendeten Variablen die doch recht große Menge der entstehenden Daten nicht mehr verarbeiten kann. Leider bin ich aber dabei überfragt welche :D .
      Ich hab heute leider keine Zeit mehr, mich darum zu kümmern, erst Morgen Abend wieder.
      Bis dahin wären ein paar mehr Infos nicht schlecht. Ich nehme an du verwendest den letzten Code aus dem ersten Beitrag? Könntest du mit dem Debugger feststellen, welche Variable genau null ist?
      Danke für deine Hilfe erstmal :D
      Ja ich verwende den letzten Code aus dem ersten Post.
      Habe nochmal ein wenig dran herumgedoktort, wie es scheint nimmt die Variable oldBuffer für Werte > 188 aus irgendeinem grund den Wert nothing an, was den Fehler verursacht.

      Sollte ich bis morgen Abend wie durch ein Wunder selbst den Fehler finden werd ichs hier posten ;)
      @ ThePlexian du hast mir grad den Tag gerettet :D

      Der Fehler war tatsächlich der Input (über den ich mir bis vorhin gar keine Gedanken gemacht habe).
      Ich hatte n simplen Gedankenfehler bei der Eingabe der Daten.
      Ich habe mithilfe einer For-Schleife eine Zahlenfolge von 1-n erzeugen lassen. Sobald diese in 2-Stellige Werte kommt wird das ganze natürlich Unfug (123456789101112).
      Habe das ganze jetzt umgeändert dass ab 9 mit a b c weitergezählt wird und es funktioniert nun. :)
      Ich hab deinen Code auch mal ausprobiert - er braucht ziemlich viel Arbeitsspeicher: 11,3 Gigabyte für das Erstellen der Permutationen für 11 Chars (geht deswegen auch nur im 64 Bit-Modus). Gibts dafür irgendeinen möglichen Grund?
      Ich habe es mal mit Bytes gemacht, um das ganze leichter bewerten zu können: 10,6GB für 11! Varianten: 265 Byte pro Auflistung. Wie brauchen 11 Bytes also im Arbeitsspeicher 265 Byte Platz?
      Nun zunächst mal hat eine objektorientierte Sprache immer einen gewissen Speicher-Overhead, also ein Byte-Array mit 11 Elementen ist auf jeden Fall größer als 11 Bytes. In .Net ist dieser Overhead noch größer als z.B. in C++, da die CLR speicher anders verwaltet und ausrichtet (so ist ein einzelnes Byte eigentlich 4 Bytes groß im nicht verwalteten Speicher, wie das in einem Array aussieht weiß ich nicht).
      Außerdem gibt es in C# den Garbage-Collector. In der Methode werden Enumeratoren und der gleichen erstellt, die die Daten in einem einzelnen Permutationszyklus effektiv kopieren. Ich habe keinen Einfluss darauf, wann diese Objekte wieder zerstört werden und deshalb kann während der Ausführung ein Vielfaches des eigentlich nötigen Speichers belegt sein.
      Wie wäre es denn, in der Funktion die einzelnen Permutationen zu yielden anstatt sie alle in eine Liste zu packen? Damit sollte sich der RAM-Verbrauch je nach Anwendung auf praktisch Null reduzieren.

      Ich habe auch mal versucht, mir deinen Code genauer anzuschauen, jedoch habe ich keinen wirklichen Ansatz finden können, da mir nicht ganz klar ist wie die Methode funktioniert. Deswegen habe ich mich mal nach anderen Methoden umgesehen, welche eine "Permutation ohne Rekursion" erlauben. Gestoßen bin ich auf "QuickPerm", einen Algorithmus welcher die Permutationen durch "Swaps" erreicht. Dieser Algorithmus gibt die Permutationen zwar in einer anderen Reihenfolge aus, in den meisten Fällen sollte dies aber nicht von Bedeutung sein. Ich poste jetzt einfach mal den Code hier, da ich es nicht für notwendig halte, extra für einen Ansatz welcher nicht von mir ist einen eigenen Thread zu erstellen.

      C#-Quellcode

      1. public static IEnumerable<T[]> Permutate<T>(this T[] input)
      2. {
      3. yield return (T[])input.Clone();
      4. T[] items = (T[])input.Clone();
      5. int[] p = Enumerable.Range(0, items.Length + 1).ToArray();
      6. for (int i = 1; i < items.Length; )
      7. {
      8. Swap(ref items[(i % 2) * --p[i]], ref items[i]);
      9. yield return (T[])items.Clone();
      10. for (i = 1; p[i] == 0; i++)
      11. {
      12. p[i] = i;
      13. }
      14. }
      15. yield break;
      16. }
      17. private static void Swap<T>(ref T item1, ref T item2)
      18. {
      19. var item = item2;
      20. item2 = item1;
      21. item1 = item;
      22. }

      Bei meinen Tests mit einem 11 Item großen Char-Array ist folgendes herausgekommen:

      ArtentusQuickPerm à la nafets
      Zeit2:16min7s
      Arbeitsspeicher11,79 GB3,09 GB

      Außerdem ist die Funktion schon mit yield erstellt, wodurch die RAM-Nutzung bei richtiger Verwendung auf praktisch 0 sinkt (wie oben erwähnt). Die Tests wurden mit einer Variante durchgeführt, welche alle Ergebnisse in einer List zwischenspeichert, um die gleichen Voraussetzungen wie Artentus zu haben.

      Hier noch ein Link zur Website, auf welcher man den Original-Code und die Erklärung finden kann: quickperm.org/

      Grüße
      Stefan
      Ich hab niemals den Anspruch erhoben, mein Code sei besonders effizient in irgend einer Hinsicht. Ich habe mir keine Drittcodes auch nur angeschaut, alles oben ist selbst ausgedacht, und ich bin nunmal alles andere als ein guter Programmierer. Von daher überrascht mich dieses Ergebnis nicht im Mindesten.
      Mein Code kann auch nicht mit Yield überarbeitet werden. Ich hatte es versucht, aber der Code bildet immer erst die Permutationen mit n - 1 Elementen, es könnte höchstens die letzte Stufe entsprechend angepasst werden. Grund ist wohl, dass ich vom rekursiven Ansatz ausgegangen bin und den dann iterativ umgesetzt habe. Alle schnellen Permutationsalgorithmen verwenden aber wohl irgend eine Art, die Elemente zu tauschen.
      also wenn ihr Kombinatoric-TheoPraxis treiben wollt, wäre ein erster Einstieg Permutationen
      Zwischenzeitlich war ich viel weiter damit, hatte alle Arten der Kombinatorik ausprogrammiert, aber die Dateien sind leider verloren.
      jdfs. neben dem (verlinkten) rekursiven allgemeingültigen Ansatz gibts noch zwei weitere - ebenso allgemeingültig:
      1. einen iterativen - Stichwort "lexikografische Permutation".
      2. und noch was ganz verdrehtes mit Zerlegung von Zahlen in ihre Faktoriellen.
        Damit kann man aus einem beliebigen Index direkt berechnen, welche lexikografische Permutation dabei rauskäme, und zwar ohne alles durchnudeln zu müssen.
      @ErfinderDesRades :
      Zu 2., das hatte ich mal gebraucht:

      C#-Quellcode

      1. public IEnumerable<T> GetNthPermutation<T>(T[] input, int n)
      2. {
      3. var indices = new List<int>();
      4. var curr = n - 1;
      5. for (var i = input.Count() - 1; i >= 0; i--)
      6. {
      7. int rem;
      8. var fact = Factorial(i);
      9. var div = Math.DivRem(curr, fact, out rem);
      10. indices.Add(div);
      11. curr = rem;
      12. }
      13. var res = new List<T>();
      14. var clone = ((T[])input.Clone()).ToList();
      15. foreach (var i in indices)
      16. {
      17. res.Add(clone[i]);
      18. clone.RemoveAt(i);
      19. }
      20. return res;
      21. }
      22. public int Factorial(int n)
      23. {
      24. var res = 1;
      25. for (var i = 1; i <= n; i++)
      26. res *= i;
      27. return res;
      28. }


      Habe das ganze jetzt mal für alle Permutationen des 11-Char-Arrays durchlaufen lassen, ergo mit ner For-Schleife mit n von 1 bis 11!, hat stolze 5:30min gedauert (habe auch nix dolles erwartet, war rein interessehalber)
      »There's no need to "teach" atheism. It's the natural result of education without indoctrination.« — Ricky Gervais

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „ThePlexian“ ()