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
Bsp.: alle Permutationen aus der Menge { 1, 2, 3 } sind
Um so etwas per Code zu realisieren bietet sich zunächst ein rekursiver Algorithmus an, da der Programmablauf dann klarer wird.
VB
C#
Dieser Code macht folgendes:
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
Bsp.: alle möglichen Kombinationen unter Verwendung von Bruteforce der Menge { 1, 2 } sind
Der Algorithmus dazu sieht so aus:
VB
C#
Dieser Code ist nun schon etwas komplizierter. Hier die Erklärung:
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.
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
Auf diesem Code können wir nun aufbauen, um unser eigentliches Ziel zu erreichen. Beachten müssen wir hierbei aber, dass bei der Permutation
Hier ist erstmal der fertige Algorithmus:
VB
C#
Erklärung:
Wir legen uns wieder die buffer an, die zusätzliche Liste ist aber aufgrund eines nicht Vorhandenseins von
Wie ich bereits sagte wird
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!
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
Um so etwas per Code zu realisieren bietet sich zunächst ein rekursiver Algorithmus an, da der Programmablauf dann klarer wird.
VB.NET-Quellcode
- Public Shared Sub PermutateRecursive(chars As IEnumerable(Of Char), ByRef result As List(Of String))
- If chars.Count() = 1 Then
- result.Add(chars.First().ToString())
- Return
- End If
- For Each c In chars
- Dim buffer = New List(Of String)()
- PermutateRecursive(chars.Except({c}), buffer)
- For Each s In buffer
- result.Add(c & s)
- Next
- Next
- End Sub
C-Quellcode
- public static void PermutateRecursive(IEnumerable<char> chars, ref List<string> result)
- {
- if (chars.Count() == 1)
- {
- result.Add(chars.First().ToString());
- return;
- }
- foreach (var c in chars)
- {
- var buffer = new List<string>();
- PermutateRecursive(chars.Except(new[] { c }), ref buffer);
- foreach (var s in buffer)
- result.Add(c + s);
- }
- }
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
Der Algorithmus dazu sieht so aus:
VB.NET-Quellcode
- Public Shared Function Bruteforce(chars As Char(), count As Integer, includeSubLists As Boolean) As String()
- If count < 1 Then Return New String(-1) {}
- Dim buffer As String()
- Dim oldBuffer = {String.Empty}
- Dim result = New List(Of String)()
- While count > 0
- count -= 1
- buffer = New String(oldBuffer.Length * chars.Length - 1) {}
- Dim index = 0
- For i = 0 To oldBuffer.Length - 1
- For j = 0 To chars.Length - 1
- buffer(index) = oldBuffer(i) & chars(j)
- index += 1
- Next
- Next
- oldBuffer = buffer
- If includeSubLists OrElse count = 0 Then result.AddRange(buffer)
- End While
- Return result.ToArray()
- End Function
C-Quellcode
- public static string[] Bruteforce(char[] chars, int count, bool includeSubLists)
- {
- if (count < 1)
- return new string[0];
- string[] buffer;
- var oldBuffer = new[] { string.Empty };
- var result = new List<string>();
- while (count > 0)
- {
- count--;
- buffer = new string[oldBuffer.Length * chars.Length];
- int index = 0;
- for (int i = 0; i < oldBuffer.Length; i++)
- for (int j = 0; j < chars.Length; j++, index++)
- buffer[index] = oldBuffer[i] + chars[j];
- oldBuffer = buffer;
- if (includeSubLists || count == 0)
- result.AddRange(buffer);
- }
- return result.ToArray();
- }
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.NET-Quellcode
- Public Shared Function Permutate(chars As Char()) As String()
- Dim buffer As String() = Nothing
- Dim oldBuffer = {String.Empty}
- For count = 0 To chars.Length - 1
- buffer = New String(If(buffer IsNot Nothing, buffer.Length, 1) * (chars.Length - count) - 1) {}
- Dim index = 0
- For i = 0 To oldBuffer.Length - 1
- For j = 0 To chars.Length - 1
- If Not oldBuffer(i).Contains(chars(j)) Then
- buffer(index) = oldBuffer(i) & chars(j)
- index += 1
- End If
- Next
- Next
- oldBuffer = buffer
- Next
- Return buffer
- End Function
C-Quellcode
- public static string[] Permutate(char[] chars)
- {
- string[] buffer = null;
- var oldBuffer = new[] { string.Empty };
- for (int count = 0; count < chars.Length; count++)
- {
- buffer = new string[(buffer != null ? buffer.Length : 1) * (chars.Length - count)];
- int index = 0;
- for (int i = 0; i < oldBuffer.Length; i++)
- for (int j = 0; j < chars.Length; j++)
- if (!oldBuffer[i].Contains(chars[j]))
- {
- buffer[index] = oldBuffer[i] + chars[j];
- index++;
- }
- oldBuffer = buffer;
- }
- return buffer;
- }
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!