Permutationen

    • Allgemein

    Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von exc-jdbi.

      Permutationen

      Eine Permutation ist eine Anordnung von Objekten in einer bestimmten Reihenfolge.
      Es gibt viele PermutationsFormen. Hier werden nur 3 besprochen, nämlich die beiden wichtigsten - die nenne ich mal "BruteForce" und "Combinatoric".
      Hinzu füge ich noch "SummandAnalyse", einfach um zu zeigen, dass sich beliebig viele PermutationsFormen ausdenken lassen.

      BruteForce
      BruteForce ist wohl am besten bekannt: Man hat einen Zeichensatz, und eine Anzahl Stellen. Bruteforce findet nun schlicht jede mögliche Art, die Zeichen auf die Stellen zu verteilen.
      Hier die Ausgabe des Zeichensatzes "0123" auf 3 Stellen:
      BruteForce(CharSetCount:=4, digitCount:=3)

      Quellcode

      1. 000
      2. 001
      3. 002
      4. 003
      5. 010
      6. 011
      7. 012
      8. 013
      9. 020
      10. 021
      11. 022
      12. 023
      13. 030
      14. 031
      15. 032
      16. 033
      17. 100
      18. 101
      19. 102
      20. 103
      21. 110
      22. 111
      23. 112
      24. 113
      25. 120
      26. 121
      27. 122
      28. 123
      29. 130
      30. 131
      31. 132
      32. 133
      33. 200
      34. 201
      35. 202
      36. 203
      37. 210
      38. 211
      39. 212
      40. 213
      41. 220
      42. 221
      43. 222
      44. 223
      45. 230
      46. 231
      47. 232
      48. 233
      49. 300
      50. 301
      51. 302
      52. 303
      53. 310
      54. 311
      55. 312
      56. 313
      57. 320
      58. 321
      59. 322
      60. 323
      61. 330
      62. 331
      63. 332
      64. 333
      Nicht wahr: Bruteforce kann jedes Kind, sobald es zählen kann ;).

      Allgemeine Permutations-Theorie am Beispiel Bruteforce
      Zählen ist ein spezieller Algorithmus, um Bruteforce durchzuführen - mehr dazu später.
      Her stelle ich erstmal allgemeinere Betrachtungen an:
      Nämlich ich betrachte Permutationen als Bäume, und zwar als Bäume mit Knoten und Blättern.
      An den Knotenpunkten im Baum gibts Unterknoten, während Blätter Endpunkte ohne Unterknoten ("Kinder") sind.
      Und die Ausgabe einer Permutation wird durch die Blätter gebildet.
      Betrachten wir alle Permutationen von "012" auf 3 Stellen genauer:

      Quellcode

      1. 000
      2. 001
      3. 002
      4. 010
      5. 011
      6. 012
      7. 020
      8. 021
      9. 022
      10. 100
      11. 101
      12. 102
      13. 110
      14. 111
      15. 112
      16. 120
      17. 121
      18. 122
      19. 200
      20. 201
      21. 202
      22. 210
      23. 211
      24. 212
      25. 220
      26. 221
      27. 222
      Auf jeder Stelle wird jedes Zeichen des Zeichensatzes durchprobiert. Aber nicht jedesmal alle Stellen gleichzeitig, sondern nach einer Änderung auf einer höherwertigen Stelle werden erstmal die dahinterliegenden niederwertigeren Stellen durchprobiert.
      Nun die Darstellung als Baum:

      Quellcode

      1. 0
      2. 00
      3. 000
      4. 001
      5. 002
      6. 01
      7. 010
      8. 011
      9. 012
      10. 02
      11. 020
      12. 021
      13. 022
      14. 1
      15. 10
      16. 100
      17. 101
      18. 102
      19. 11
      20. 110
      21. 111
      22. 112
      23. 12
      24. 120
      25. 121
      26. 122
      27. 2
      28. 20
      29. 200
      30. 201
      31. 202
      32. 21
      33. 210
      34. 211
      35. 212
      36. 22
      37. 220
      38. 221
      39. 222
      Man erkennt: Die Änderungen der höherwertigen Stellen sind Knoten, deren jeder 3 "Kinder" gebiert. Nur die kind-losen Knoten, die Blätter, gehören zur Ausgabe der Permutation.

      Damit ist ein glaub sehr allgemeiner Algorithmus gegeben zur rekursiven Implementation verschiedenster Permutationen:
      Aus einer Anordnung (Permutation) können Kind-Anordnungen generiert werden, die selbst wieder zum Generieren weiterer Kind-Anordnungen verwendet werden.
      "Kinderlose" Permutationen hingegen bilden die Ausgabe.


      Dieses umgesetzt am Beispiel Bruteforce:

      VB.NET-Quellcode

      1. Public Sub BruteForce(charSetCount As Integer, digitCount As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
      2. 'Jede digit-Stelle permutiert den Charset durch, und gebiert also charSetCount "Kinder". Die Kinder werden eine Stelle weiter permutiert.
      3. 'Auf unterster Ebene (position=digitCount) erfolgt statt weiterer Vertiefung die Ausgabe.
      4. Console.WriteLine(String.Concat("BruteForce(charSetCount:=", CharSetCount, ",digitCount:=", digitCount, ")"))
      5. Dim recurse As Action(Of Integer, Integer()) = Nothing
      6. recurse = _
      7. Sub(position As Integer, arr As Integer())
      8. If position = digitCount Then 'Bedingung für "Kinderlosigkeit"
      9. outputCallback(arr)
      10. Else
      11. For i = 0 To charSetCount - 1
      12. Dim arr2 = arr.CloneX
      13. arr2(position) = i
      14. recurse(position + 1, arr2) 'selbst-Aufruf mit dem neuen Array - permutiert wird eine Stelle weiter
      15. Next
      16. End If
      17. End Sub
      18. Dim digits(digitCount - 1) As Integer
      19. recurse(0, digits)
      20. End Sub
      Man muß sich also 2 Dinge überlegen:
      1. wie werden aus einer Permutation "Kinder" generiert?
      2. wann tritt "Kinderlosigkeit" ein?


      Combinatoric
      "Combinatoric", die zweite wichtige Permutationsform ist viel schwieriger: Hier werden immer alle Zeichen des Zeichensatzes vollständig ausgegeben, jedoch in immer anderen Reihenfolgen.
      Praktische Anwendung findet Combinatorik beim Durchprobieren aller möglichen Wege über mehrere Stationen oder beim Händeschütteln einer Gruppe von Menschen.
      Da alle Zeichen in jeder Permutation enthalten sind, ist also die Stellen-Zahl bei Combinatoric mit der Zeichensatz-Anzahl identisch.
      Und anders als bei BruteForce muß man immer an 2 Stellen ändern, nämlich 2 Zeichen müssen ihre Plätze tauschen.
      1. wie werden aus einer Permutation "Kinder" generiert?
        von einer Stelle aus wird sukzessive gegen alle niederwertigeren Stelle getauscht
      2. wann tritt "Kinderlosigkeit" ein?
        wenn die Stelle, von der getauscht wird, die niederwertigste ist (position = charSetCount)
      Der Algo:

      VB.NET-Quellcode

      1. Public Sub Combinatoric(charSetCount As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
      2. 'Jede Stelle gebiert "Kinder", indem sie mit allen folgenden Stellen vertauscht wird. Die Kinder werden eine Stelle weiter permutiert.
      3. 'Auf unterster Ebene (position=charSetCount) erfolgt statt weiterer Vertiefung die Ausgabe.
      4. Console.WriteLine(String.Concat("Combinatoric(charSetCount:=", charSetCount, ")"))
      5. Dim recurse As Action(Of Integer, Integer()) = Nothing
      6. recurse = _
      7. Sub(position As Integer, arr As Integer())
      8. If position = charSetCount Then 'Bedingung für "Kinderlosigkeit"
      9. outputCallback(arr)
      10. Else
      11. recurse(position + 1, arr) 'das Original-Array ohne Tauschvorgang ist auch ein "Kind"
      12. For i = position + 1 To charSetCount - 1
      13. Dim arr2 = arr.CloneX
      14. arr2.Swap(position, i)
      15. recurse(position + 1, arr2) 'selbst-Aufruf mit dem neuen Array - permutiert wird eine Stelle weiter
      16. Next
      17. End If
      18. End Sub
      19. Dim digits = Enumerable.Range(0, charSetCount).ToArray 'Array mit charSetCount verschiedenen Zahlen
      20. recurse(0, digits)
      21. End Sub
      24 Möglichkeiten, 4 Objekte unterschiedlich anzuordnen

      Quellcode

      1. Combinatoric(charSetCount:=4)
      2. 0123
      3. 0132
      4. 0213
      5. 0231
      6. 0321
      7. 0312
      8. 1023
      9. 1032
      10. 1203
      11. 1230
      12. 1320
      13. 1302
      14. 2103
      15. 2130
      16. 2013
      17. 2031
      18. 2301
      19. 2310
      20. 3120
      21. 3102
      22. 3210
      23. 3201
      24. 3021
      25. 3012


      Summanden-Analyse
      Dieses Beispiel hat keinen mir bekannten Nutzen, ausser, dasses aufzeigt, dass sich alle möglichen Permutationsformen ausdenken lassen:
      1. wie werden aus einer Permutation "Kinder" generiert?
        Bekannt sind die bisherige Summe (currSum) und die Zielsumme (targetSum)
        Es werden nun sukzessive der gleichen Liste jeweils andere Summanden zugefügt, von 1 bis zur Zielsummen-Differenz
      2. wann tritt "Kinderlosigkeit" ein?
        wenn die bisherige Summe die Zielsumme erreicht hat (currSum = targetSum)

      VB.NET-Quellcode

      1. Public Sub SummandAnalize(targetSum As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
      2. 'eine Liste gebiert Kinder, indem ein Summand zugefügt wird, der sukzessive von 1 bis zur Zielsummen-Differenz geändert wird.
      3. 'hier die Optimierung, dass immer dieselbe list verwendet wird.
      4. Console.WriteLine(String.Concat("SummandAnalize(targetSum:=", targetSum, ")"))
      5. Dim list As New List(Of Integer)
      6. Dim recurse As Action(Of Integer) = Nothing
      7. recurse = _
      8. Sub(currSum As Integer)
      9. If currSum = targetSum Then 'Bedingung für "Kinderlosigkeit"
      10. outputCallback(list)
      11. Else
      12. list.Add(0)
      13. For i = 1 To targetSum - currSum
      14. list(list.Count - 1) = i
      15. recurse(currSum + i)
      16. Next
      17. list.RemoveAt(list.Count - 1) 'da immer dieselbe list verwendet wird zum Rekursions-Ausgang die Zufügung rückgängig machen.
      18. End If
      19. End Sub
      20. recurse(0)
      21. End Sub
      Ausgabe:

      Quellcode

      1. SummandAnalize(targetSum:=5)
      2. 11111
      3. 1112
      4. 1121
      5. 113
      6. 1211
      7. 122
      8. 131
      9. 14
      10. 2111
      11. 212
      12. 221
      13. 23
      14. 311
      15. 32
      16. 41
      17. 5

      Anzahl der Permutationen
      • Bei Bruteforce multipliziert jede Stelle die Anzahl mit der Mächtigkeit des Zeichensatzes.
        Also beim Zeichensatz "0123" und 3 Stellen ergeben sich 4*4*4 = 4^3 = 64 Permutationen

      • Bei Combinatoric multipliziert jede Stelle ihre Wertigkeit mit der Permutations-Anzahl, die sich aus den niedrigeren Wertigkeiten ergibt
        also beim Zeichensatz "0123" ergibt sich 1*2*3*4 = 4! = 24 Permutationen
        Kann man sich vlt. am Beispiel Wegfindung über Stationen plausibel machen:
        Angenommen die Stationen A, B.
        Da hat man 2 mögliche Startpunkte: man kann von A nach B fahren oder von B nach A.
        Hinzu kommt die Station C
        Nun hat man 3 mögliche Startpunkte, man kann von C zunächst nach A, dann B fahren, oder von C zunächst nach B, dann A.
        Und ebenso siehts von den anneren Startpunkten aus, sodass sich insgesamt 3*2 Möglichkeiten ergeben, d.i. 3!.
        Und bei 4 Stationen hat jede der 4 Stationen als Startort alle Möglichkeiten der Dreier-Variante, also 4*3*2 = 4! = 24

      • Bei Summanden-Analyse weiß ich nicht, wie das ausrechnen, und obs ühaupt möglich ist.


      Optimierungen
      • Bruteforce "zählen"

        VB.NET-Quellcode

        1. Public Sub CountUpBruteForce(charSetCount As Integer, digitCount As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
        2. 'Zählen ist eigentlich ein iterativer Vorgang, das ist garnet rekursiv:
        3. 'man stelle sich ein Zählwerk vor: die letzte Ziffer wird immer hochgezählt
        4. 'beim Nulldurchgang jedweder Ziffer wird die vorherige Ziffer auch hochgezählt
        5. 'zb bei 2299 ereignen sich 2 nulldurchgänge, sodass die letzten 3 ziffern hochgezählt werden -> 2300
        6. Console.WriteLine(String.Concat("CountUpBruteForce(charSetCount:=", charSetCount, ",digitCount:=", digitCount, ")"))
        7. Dim rotatingDigit = digitCount - 1
        8. Dim digits(rotatingDigit) As Integer
        9. While rotatingDigit >= 0
        10. outputCallback(digits)
        11. For rotatingDigit = digits.Count - 1 To 0 Step -1
        12. digits(rotatingDigit) += 1
        13. If (digits(rotatingDigit) < charSetCount) Then Exit For
        14. digits(rotatingDigit) = 0
        15. Next
        16. End While
        17. End Sub

      • Combinatoric InPlace

        VB.NET-Quellcode

        1. Public Sub InplaceCombinatoric(digitCount As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
        2. 'Optimierung: Es kann immer dasselbe Array verwendet werden, wenn nach TauschVorgang und Rekursion der Tauschvorgang wieder zurückgetauscht wird.
        3. Console.WriteLine(String.Concat("InplaceCombinatoric(digitCount:=", digitCount, ")"))
        4. Dim digits = digitCount.Times.ToArray
        5. Dim recurse As Action(Of Integer) = Nothing
        6. recurse = _
        7. Sub(position As Integer)
        8. If position = digitCount Then
        9. outputCallback(digits)
        10. Else
        11. recurse(position + 1)
        12. For i = position + 1 To digitCount - 1
        13. digits.Swap(position, i)
        14. recurse(position + 1)
        15. digits.Swap(position, i)
        16. Next
        17. End If
        18. End Sub
        19. recurse(0)
        20. End Sub

      • Summanden-Analyse ohne Test auf "Kinderlosigkeit"

        VB.NET-Quellcode

        1. Public Sub SummandAnalizeOptimized(targetSum As Integer, outputCallback As Action(Of IEnumerable(Of Integer)))
        2. 'Optimierung: Es werden nur die Kinder generiert, die targetSum nicht erreichen. Das Kind, welches targetSum erreicht, wird direkt ausgegeben.
        3. Console.WriteLine(String.Concat("SummandAnalizeOptimized(targetSum:=", targetSum, ")"))
        4. Dim list As New List(Of Integer)
        5. Dim recurse As Action(Of Integer) = Nothing
        6. recurse = _
        7. Sub(currSum As Integer)
        8. Dim missing = targetSum - currSum
        9. list.Add(0)
        10. For i = 1 To missing - 1
        11. list(list.Count - 1) = i
        12. recurse(currSum + i)
        13. Next
        14. list(list.Count - 1) = missing 'targetSum erreicht
        15. outputCallback(list)
        16. list.RemoveAt(list.Count - 1)
        17. End Sub
        18. recurse(0)
        19. End Sub


      Der outputCallback
      Meine Implementations-Beispiele haben ja meist eine rekursive anonyme Methode, und daher ein Problem ein Ergebnis, nämlich ein Blatt, zurückzugeben.
      Daher gebe ich den Methoden einen outputCallback As Action(Of IEnumerable(Of Integer)) mit, also ich gebe eine Methode mit hinein, die aufgerufen und der ein Blatt-Ergebnis mitgegeben werden kann, ohne die Rekursion zu verlassen.
      Im Aufrufer der PermutationsMethode ist dann die Verarbeitung dieses Ergebnisses implementiert - hier einfach eine Ausgabe auf die Konsole:

      VB.NET-Quellcode

      1. Public Sub Main()
      2. Dim callback As Action(Of IEnumerable(Of Integer)) = Sub(perm) Console.WriteLine(String.Concat(perm))
      3. 'BruteForce(3, 3, callback)
      4. CountUpBruteForce(3, 3, callback)
      5. 'SummandAnalizeOptimized(5, callback)
      6. 'Combinatoric(4, callback)
      7. Console.ReadKey()
      8. End Sub
      Dateien
      • Permutation.zip

        (11,35 kB, 238 mal heruntergeladen, zuletzt: )

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „ErfinderDesRades“ ()

      Baum-Logs der Permutationen

      Ich hab mal spasseshalber die hierarchischen Logs aller 3 rekursiven Permutationen veranschaulicht. Dabei kann man den jeweiligen Algo bischen nachvollziehen, wenn man den Baum ebenen-Weise ansieht, also eher in vertikaler Sichtweise statt der üblichen Lesung von links nach rechts. Die Kommentare beziehen sich auf die entsprechende vertikale Ebene

      BruteForce: Jede Ebene probiert jeden Char auf ihrer Position durch: Bei 3 Chars und 3 Positionen ergibt das 3*3*3 = 3^3 Permutationen
      Die Berechnung der Anzahl der Permutationen veranschaulicht sich auch durch die Anzahlen der Elemente pro Ebene und Zweig (3, 3, 3)

      VB.NET-Quellcode

      1. BruteForce: Jede Ebene probiert jeden Char auf ihrer Position durch: Bei 3 Chars und 3 Positionen ergibt das 3*3*3 = 3^3 Permutationen
      2. 0 'probiere die Zahlen 0-2 an Index 0 durch
      3. 00 'probiere die Zahlen 0-2 an Index 1 durch
      4. 000 'probiere die Zahlen 0-2 an Index 2 durch
      5. 001
      6. 002
      7. '\probiere die Zahlen 0-2 an Index 2 durch
      8. 01
      9. 010
      10. 011
      11. 012
      12. 02
      13. 020
      14. 021
      15. 022
      16. '\probiere die Zahlen 0-2 an Index 1 durch
      17. 1
      18. 10
      19. 100
      20. 101
      21. 102
      22. 11
      23. 110
      24. 111
      25. 112
      26. 12
      27. 120
      28. 121
      29. 122
      30. 2
      31. 20
      32. 200
      33. 201
      34. 202
      35. 21
      36. 210
      37. 211
      38. 212
      39. 22
      40. 220
      41. 221
      42. 222
      43. '\probiere die Zahlen 0-2 an Index 0 durch

      Combinatoric: Jede Ebene tauscht den Char auf ihrer Position mit allen Folge-Positionen: Bei 3Chars und 4 Positionen ergibt das 4*3*2 = 4! Permutationen
      Die Berechnung der Anzahl der Permutationen veranschaulicht sich auch durch die Anzahlen der Elemente pro Ebene und Zweig (4, 3, 2)

      VB.NET-Quellcode

      1. Combinatoric: Jede Ebene tauscht den Char auf ihrer Position mit allen Folge-Positionen: Bei 3 Chars und 4 Positionen ergibt das (1*)2*3*4 = 4! Permutationen
      2. 0123 'vertausche nacheinander die 0 an Index 0 mit den Positionen 1, 2, 3
      3. 0123 'vertausche nacheinander die 1 an Index 1 mit den Positionen 2, 3
      4. 0123 'vertausche nacheinander die 2 an Index 2 mit der Position 3
      5. 0123 '(ungetauscht ist auch eine gültige Variation)
      6. 0132
      7. '\vertausche nacheinander die 2 an Index 2 mit der Position 3
      8. 0213
      9. 0213
      10. 0231
      11. 0321
      12. 0321
      13. 0312
      14. '\vertausche nacheinander die 1 an Index 1 mit den Positionen 2, 3
      15. 1023
      16. 1023
      17. 1023
      18. 1032
      19. 1203
      20. 1203
      21. 1230
      22. 1320
      23. 1320
      24. 1302
      25. 2103
      26. 2103
      27. 2103
      28. 2130
      29. 2013
      30. 2013
      31. 2031
      32. 2301
      33. 2301
      34. 2310
      35. 3120
      36. 3120
      37. 3120
      38. 3102
      39. 3210
      40. 3210
      41. 3201
      42. 3021
      43. 3021
      44. 3012
      45. '\vertausche nacheinander die 0 an Index 0 mit den Positionen 1, 2, 3

      SummandAnalyse: eine eigenartige Schlangenlinie mit irgendwie systematisch unterschiedlich starken Ausschlägen
      SummandAnalyse finde ich besonders interessant, wegen der eigenartigen selbstähnlichen Struktur der sich ergebenden "Schlangenlinie". Beachte: alle kindlosen Knoten haben Summe 6 - ich habe sie zusätzlich mit ° markiert.

      VB.NET-Quellcode

      1. SummandAnalyse von 6: alle kindlosen Knoten haben Summe 6
      2. 1 'probiere die Zahlen 1 - 6 an Index 0
      3. 11 'probiere 1 - 5 an Index 1
      4. 111 'probiere 1 - 4 an Index 2
      5. 1111 'probiere 1 - 3 an Index 3
      6. 11111 'probiere 1 - 2 an Index 4
      7. ° 111111
      8. ° 11112
      9. 1112
      10. ° 11121
      11. ° 1113
      12. 112
      13. 1121
      14. ° 11211
      15. ° 1122
      16. 113
      17. ° 1131
      18. ° 114
      19. 12
      20. 121
      21. 1211
      22. ° 12111
      23. ° 1212
      24. 122
      25. ° 1221
      26. ° 123
      27. 13
      28. 131
      29. ° 1311
      30. ° 132
      31. 14
      32. ° 141
      33. ° 15
      34. 2
      35. 21 'probiere 1 - 4 an Index 1
      36. 211 'probiere 1 - 3 an Index 2
      37. 2111 'probiere 1 - 2 an Index 3
      38. ° 21111
      39. ° 2112
      40. 212
      41. ° 2121
      42. ° 213
      43. 22
      44. 221
      45. ° 2211
      46. ° 222
      47. 23
      48. ° 231
      49. ° 24
      50. 3
      51. 31
      52. 311
      53. ° 3111
      54. ° 312
      55. 32
      56. ° 321
      57. ° 33
      58. 4
      59. 41
      60. ° 411
      61. ° 42
      62. 5
      63. ° 51
      64. ° 6

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

      Das "BruteForce" heißt eigentlich "Variation mit Wiederholung" und das "Combinatoric" ist in der Tat eine "Permutation ohne Wiederholung". Eine Variation ist aber keine Permutation. Eine Variation liegt dann vor, wenn nicht alle Objekte aus der zu variierenden Menge ausgewählt werden.

      Außerdem: Deine Algorithmen können nur Variationen bzw. Permutationen aus einem diskreten Intervall [0, n] berechnen. Interessant wären aber beliebige Mengen, z.B. {1,2,10,100,123} oder gar {"a", "test", "xyz", "bla", "foo", "bar"}.

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

      Jo, meine "Begriffe" sind nicht ganz auffm Stand der Mathematik.
      ZB. meine "Summanden-Analyse" liegt bestimmt ausserhalb von allem, was in der Mathematik als Permutation, Kombination, Variation or whatever definiert ist (Dennoch wurde grad das neulich nachgefragt). Ich glaub, wenn ich "Permutation" sage, dann meine ich ganz allgemein das Generieren einer tw. auch großen, aber endlichen Menge gleichartiger, aber unterscheidbarer kleinen Mengen, die gewisse Kriterien erfüllen.

      Vielen Dank für den Wiki-Link, da sollte die Geschichte vom mathematischen Standpunkt aus korrekt definiert sein.

      Quadsoft schrieb:

      Deine Algorithmen können nur Variationen bzw. Permutationen aus einem diskreten Intervall [0, n] berechnen. Interessant wären aber beliebige Mengen, z.B. {1,2,10,100,123} oder gar {"a", "test", "xyz", "bla", "foo", "bar"}.
      Da sehe ich eigentlich kein Problem - ist doch nur eine Fingerübung:
      Statt eine "beliebige Menge" zu permutieren permutiere ich wie gehabt meine Integer-Arrays, und verwende sie als Indizees der beliebigen Menge:

      VB.NET-Quellcode

      1. Public Sub Main()
      2. Dim anyThings = "ha he hi ho".Split
      3. Dim callback As Action(Of IEnumerable(Of Integer)) = Sub(perm) Console.WriteLine(String.Join(" ", perm.Select(Function(i) anyThings(i))))
      4. Combinatoric(anyThings.Length, callback)
      5. Console.ReadKey()
      6. End Sub
      Ausgabe

      Quellcode

      1. ha he hi ho
      2. ha he ho hi
      3. ha hi he ho
      4. ha hi ho he
      5. ha ho hi he
      6. ha ho he hi
      7. he ha hi ho
      8. he ha ho hi
      9. he hi ha ho
      10. he hi ho ha
      11. he ho hi ha
      12. he ho ha hi
      13. hi he ha ho
      14. hi he ho ha
      15. hi ha he ho
      16. hi ha ho he
      17. hi ho ha he
      18. hi ho he ha
      19. ho he hi ha
      20. ho he ha hi
      21. ho hi he ha
      22. ho hi ha he
      23. ho ha hi he
      24. ho ha he hi

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

      Permutieren mit dem Iterator-Feature (ab 2012)

      Obige Permutatoren arbeiten ja mit dem etwas ungewöhnlichen Konstrukt, dass ein callBack in die Methode reingegeben wird, mit dem die einzelnen Permutationen quasi "zurückgeschickt" werden.
      Seit 2012 gibts auch in vb.net das Yield-Feature, mit dem eine Methode viele Ergebnisse zurückschicken kann, welchen dann einfach mit ForEach-Durch-Schleifbar sind.
      Ich hab das mal für die BruteForce-Permutation implementiert:

      VB.NET-Quellcode

      1. Public Sub Main2()
      2. For Each perm In BruteForceIterator(3, 4)
      3. Console.WriteLine(String.Concat(perm))
      4. Next
      5. End Sub
      6. Public Iterator Function BruteForceIterator(ByVal charSetCount As Integer, ByVal digitCount As Integer) As IEnumerable(Of Integer())
      7. If digitCount = 0 Then Yield New Integer() {} : Return 'eine einzige, leere Permutation yielden
      8. Dim uBounds = digitCount - 1
      9. Dim perm(uBounds) As Integer
      10. For Each parentPerm In BruteForceIterator(charSetCount, uBounds)
      11. Array.Copy(parentPerm, perm, uBounds)
      12. For i = 0 To charSetCount - 1
      13. perm(uBounds) = i
      14. Yield perm
      15. Next
      16. Next
      17. End Function
      Dieses stellt auch insofern eine Veränderung dar, dass ich die Rekursion nicht als lokale anonyme Methode formuliert habe, sondern als "richtige" rekursive Methode.
      Hat den Nachteil, dass in jedem Selbstaufruf der charSetCount-Parameter mit durchgeschleppt werden muss, obwohl der sich niemals ändert.

      Edit: nochmal nachgedacht, und gefunden, wie es auch mit lokaler rekursiver Iterator-Funktion geht:

      VB.NET-Quellcode

      1. Public Function BruteForceLocalIterator(ByVal charSetCount As Integer, ByVal digitCount As Integer) As IEnumerable(Of Integer())
      2. Dim recurse As Func(Of Integer, IEnumerable(Of Integer())) = _
      3. Iterator Function(digits)
      4. If digits = 0 Then Yield New Integer() {} : Return 'eine einzige, leere Permutation yielden
      5. Dim uBounds = digits - 1
      6. Dim perm(uBounds) As Integer
      7. For Each parentPerm In recurse(uBounds)
      8. Array.Copy(parentPerm, perm, uBounds)
      9. For i = 0 To charSetCount - 1
      10. perm(uBounds) = i
      11. Yield perm
      12. Next
      13. Next
      14. End Function
      15. Return recurse(digitCount)
      16. End Function

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

      Ich weiß dass der Beitrag schon etwas älter ist, allerdings wollte ich hierzu noch eine neuere Methode vorstellen.

      Mit LINQ kann man ziemlich einfach alle Kombinationen einer List holen:

      VB.NET-Quellcode

      1. ​Dim range = {0, 1, 2, 3}
      2. Dim combinations = From a In range
      3. From b In range
      4. From c In range
      5. Select (a, b, c) ' Permutation mit Wiederholung


      Das Select(a, b, c) ist die neue Tuple Syntax (ab .NET 4.7). Frühere Versionen können new Tuple(of Integer, Integer, Integer)(a, b, c) verwenden.

      Hier noch ein paar Beispiele wie man Permutation ohne Wiederholung und Permutation von zwei unterschiedlichen Listen umsetzt. Inkl zwei Extension Methods um Ranges zu erstellen bzw. auszugeben:
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Imports System.Runtime.CompilerServices
      2. Module Module1
      3. ' ################################################################
      4. ' ######################### Permutations #########################
      5. ' ################################################################
      6. Sub PermutationWithRepetition(ByVal range As IEnumerable)
      7. Dim combinations = From a In range
      8. From b In range
      9. Select (a, b)
      10. combinations.Print()
      11. End Sub
      12. Sub PermutationWithRepetitionList()
      13. PermutationWithRepetition({0, 1, 2, 3})
      14. End Sub
      15. Sub PermutationWithRepetitionRange()
      16. PermutationWithRepetition(0.To(5, [step]:=1))
      17. End Sub
      18. Sub PermutationWithoutRepetition()
      19. Dim list = {0, 1, 2, 3}
      20. Dim combinations = From a In list
      21. From b In list.Except({a})
      22. From c In list.Except({a, b})
      23. From d In list.Except({a, b, c})
      24. Select (a, b, c, d)
      25. combinations.Print()
      26. End Sub
      27. Sub PermutationWithRepetitionTwoLists()
      28. Dim list1 = {0, 1, 2, 3}
      29. Dim list2 = {4, 5, 6, 7}
      30. Dim combinations = From x In list1
      31. From y In list2
      32. Select (x, y)
      33. combinations.Print()
      34. End Sub
      35. ' ################################################################
      36. ' ################ Main Method and Helper Methods ################
      37. ' ################################################################
      38. Sub Main()
      39. Dim functions As New Dictionary(Of String, Action) From {
      40. {"Exit", Sub() Environment.Exit(0)} 'default action
      41. }
      42. functions.AddRange(
      43. {
      44. AddressOf PermutationWithRepetitionList,
      45. AddressOf PermutationWithRepetitionRange,
      46. AddressOf PermutationWithoutRepetition,
      47. AddressOf PermutationWithRepetitionTwoLists
      48. })
      49. While True
      50. Console.WriteLine("Choose function to execute")
      51. For i As Integer = 0 To functions.Count - 1
      52. Console.WriteLine("({0}) {1}", i, functions.ElementAt(i).Key)
      53. Next
      54. Console.WriteLine("")
      55. Console.Write("> ")
      56. Dim input As String = Console.ReadLine()
      57. Try
      58. functions.ElementAt(Integer.Parse(input)).Value.Invoke()
      59. Catch ex As Exception
      60. Console.WriteLine("Invalid number")
      61. End Try
      62. Console.WriteLine("")
      63. Console.WriteLine("")
      64. End While
      65. End Sub
      66. <Extension()>
      67. Sub AddRange(ByRef dict As Dictionary(Of String, Action), ByRef actions As IEnumerable(Of Action))
      68. For Each action In actions
      69. dict.Add(action.Method.Name, action)
      70. Next
      71. End Sub
      72. <Extension()>
      73. Public Function [To](ByVal start As Integer, ByVal [end] As Integer, Optional ByVal [step] As Integer = 1) As IEnumerable(Of Integer)
      74. Return From x In Enumerable.Range(start, [end] + 1) Where (x - start) Mod [step] = 0 OrElse x - start = 0
      75. End Function
      76. <Extension()>
      77. Sub Print(Of T)(ByRef combinations As IEnumerable(Of T))
      78. combinations.ToList.ForEach(Sub(i) Console.WriteLine("{0}", i))
      79. End Sub
      80. End Module
      SWYgeW91IGNhbiByZWFkIHRoaXMsIHlvdSdyZSBhIGdlZWsgOkQ=

      Weil einfach, einfach zu einfach ist! :D

      Bitwise Permutation mit Wiederholung, Lexikographisch

      Bitwise Permutation mit Wiederholung, Lexikographisch

      Die Bitwise Permutation mit Wiederholung arbeitet mit einer Zahl (primitiven Datentype: byte, int32, etc.) und Bitwise-Operationen, daher auch der Name Bitwise.

      Gegeben ist also eine Zahl, z.B. eine Byte Zahl wie 176. Die Bit-Repräsentation ist 10110000. Wie man erkennen kann sind 3 Bits von 8 Bits gesetzt, d.h. k1 = 3. Oder umgekehrt, es sind 5 Bits nicht gesetzt (k0 = 8 - k1 = 5).

      Warum das es sich um eine Permutation mit Wiederholung handelt, erkennt man wiederum an der Bit-Repräsentation. In dieser Anordnung gibt es Zahlen die sich wiederholen. Da es sich um eine Bit-Anordnung handelt, können es nur die Zahlen 0 oder 1 sein.

      Für die Umsetzung der Bitwise Permutation mit Wiederholung, nutzt man gerne die Lexikographische Ordnung, da sie sehr schnell ist, und man so auf die Rekursive Anordnung verzichten kann. Damit das funktioniert muss jedoch die Startzahl berechnet werden.
      z.B. k1 = 3 somit start = 7 (00000111) was 2^k1 - 1 entspricht.


      Vorteil Lexikographische Lösung

      Vielleicht doch noch ein paar Worte zur Lexikographische Lösung. Angenommen man nähme die naive rekursive Lösung. Man würde sofort erkennen, dass die Umsetzung nicht so einfach ist, da Zahlen in der Menge sind, die mehrmals vertreten sein können und das an verschiedensten Positionen. Auch da wäre die einfachste Lösung über eine Sortierung der Menge, die auf die Gesamtheit betrachtet den niedrigsten Wert besitzt (also wiederum 00000111) oder einfach 2^k1 - 1.

      Und wen man schon so weit ist, kann man sich auch gleich die Überlegung machen, ob dann die Lexikographische Lösung nicht doch die beste Alternative davon ist, denn nebst iterative Ansatz gibt es weitere Vorteile:

      Im schlimmsten Fall hat der Algorithmus zur Berechnung der nächsten lexikographischen Permutation eine Zeitkomplexität von Θ(n) und im Idealfall eine Zeitkomplexität von Θ(1).
      Durchschnittlich kann gesagt werden, dass für jede Berechnung zur nächsten Permutation eine Laufzeit von Θ(n! × n) erforderlich ist.


      Funktion Bitwise Lexikographische Lösung

      start = Startwert
      BR = Bit-Repräsentation

      • a: Suche in start in BR das erste gesetzte Bit, und sofern vorgängig Nullen vorhanden sind, setze die entsprechenden Bits. Ist das gemacht, zähle zum gefunden numerischen Wert 1 dazu.
      • b: Suche in a in BR das erste gesetzte Bit, und merke dir den numerischen Wert.
      • c: Suche in start in BR das erste gesetzte Bit und 'div' den numerischen Wert mit 2, und merke dir diesen Wert.
      • d: Teile b und c als numerische Werte miteinenader und zähle 1 ab.
      • e: Addiere a und d als numerische Werte, und gib den Wert als konvertierter Datentype zurück.


      Anzahl Permutationen

      Die Anzahl der Permutationen lässt sich ganz normal über die Formel für die Permutation mit Wiederholung berechnen.


      Werkzeuge für die Berechnung der Anzahl Permutationen

      VB.NET-Quellcode

      1. Private Function ToNumberOfPermutation(number As Byte, size As Int32) As UInt32
      2. Dim k1 = CountBitsSet(number)
      3. Dim k0 = size - k1
      4. Dim result = Factorial(Convert.ToUInt64(size))
      5. result \= Factorial(Convert.ToUInt64(k0))
      6. result \= Factorial(Convert.ToUInt64(k1))
      7. Return Convert.ToUInt32(result)
      8. End Function
      9. Private Function Factorial(number As UInt64) As UInt64
      10. Dim result As UInt64 = 1
      11. If number = 0 OrElse number = 1 Then
      12. result = 1
      13. Else
      14. For i As UInt64 = 1 To number
      15. result *= i
      16. Next
      17. End If
      18. Return result
      19. End Function

      C#-Quellcode

      1. private static uint ToNumberOfPermutation(uint number, int size)
      2. {
      3. var k1 = CountBitsSet(number);
      4. var k0 = size - k1;
      5. ulong result = Factorial((ulong)size);
      6. result /= Factorial((ulong)k0);
      7. result /= Factorial((ulong)k1);
      8. return (uint)result;
      9. }
      10. private static ulong Factorial(ulong number)
      11. {
      12. ulong result = 1;
      13. if (number == 0 || number == 1)
      14. result = 1;
      15. else
      16. for (ulong i = 1; i <= number; i++)
      17. result *= i;
      18. return result;
      19. }



      EDR hat in dem Sinne in den obigen Beiträgen schon sehr viel über Permutationen geschrieben. Wer sich weiter informieren will, hier noch ein paar Links.
      de.wikipedia.org/wiki/Lexikographische_Ordnung
      mathebibel.de/permutation-mit-wiederholung
      de.wikipedia.org/wiki/Permutat…mutation_mit_Wiederholung


      Und zuletzt noch der Code. Es ist eine Byte Variante. Alle Funktionen können natürlich auch für andere primitive Datentypen umgeändert werden.


      Freundliche Grüsse

      exc-jdbi

      Vb.Net - Bitwise Permutation mit Wiederholung Lexikographisch

      VB.NET-Quellcode

      1. Option Strict On
      2. Option Explicit On
      3. 'Es handelt sich hier um eine Bitwise Permutation mit Repetition,
      4. 'da mehrere 1 oder 0 in der Bit-Repräsentation vorhanden sind.
      5. 'Sobald die Zahl 0 (00000000) oder 255 (11111111) ist, wird abgebrochen,
      6. 'da man in der Bit-Räpräsentation nur eine sich wiederholende Zahl findet.
      7. 'Da die Bitwise PermutationWR lexikographisch erfolgt, muss mit
      8. 'einer Startzahl begonnen werden. (N = Anzahl gesetzte Bits)
      9. 'Z.B. N = 2 >>> start = 3
      10. 'Z.B. N = 3 >>> start = 7
      11. Namespace BitwisePermutationTest
      12. Public Module Program
      13. Public Sub Main()
      14. TestBitwisePermutationWRLexicoBytes()
      15. Console.ReadLine()
      16. End Sub
      17. Private Sub TestBitwisePermutationWRLexicoBytes()
      18. Dim k1 As Int32, i = 1, cnt = Byte.MaxValue
      19. Dim value = Convert.ToByte(Rand.Next(256))
      20. 'darf nicht 0 oder 255 sein
      21. If value = 0 OrElse value = 255 Then PrintOutNoPermutationsWR(value)
      22. If value > 0 AndAlso value < 255 Then
      23. Console.Write(value)
      24. Console.Write($" {Convert.ToString(value, 2)}")
      25. k1 = CountBitsSet(value)
      26. Console.WriteLine($" k1 = {k1}")
      27. Console.WriteLine()
      28. 'Da die Bitwise PermutationWR lexikographisch erfolgt,
      29. 'muss mit einer Startzahl begonnen werden.
      30. Dim start = ToStartNumber(k1)
      31. Console.WriteLine($"{start,-4} {Convert.ToString(start, 2)}")
      32. For i = 1 To cnt - 1
      33. start = BitwisePermutationWRLexico(start)
      34. If start = Byte.MaxValue Then Exit For
      35. Console.WriteLine($"{start,-4} {Convert.ToString(start, 2)}")
      36. Next
      37. End If
      38. Console.WriteLine($"count = {i}")
      39. Console.WriteLine()
      40. End Sub
      41. Private Sub PrintOutNoPermutationsWR(value As Int32)
      42. Console.Write($"One permutations: value = {value} ")
      43. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2)}")
      44. End Sub
      45. Private Function CountBitsSet(number As Byte) As Int32
      46. 'Anzahl der gesetzten Bits in der Zahl.
      47. 'http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
      48. Dim result = 0I ' result accumulates the total bits set in v
      49. While Not number = 0
      50. ' clear the least significant bit set
      51. number = Convert.ToByte(number And number - 1)
      52. result += 1
      53. End While
      54. Return result
      55. End Function
      56. Private Function BitwisePermutationWRLexico(number As Byte) As Byte
      57. 'http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
      58. Dim t = Convert.ToByte(((number Or number - 1) + 1) And 255)
      59. Return Convert.ToByte((t Or ((t And -t) \ (number And -number) >> 1) - 1) And 255)
      60. End Function
      61. Private Function ToStartNumber(n As Int32) As Byte
      62. Dim s = New String("1"c, n)
      63. Return Convert.ToByte(s, 2)
      64. End Function
      65. End Module
      66. End Namespace
      67. Public Module RandomHolder
      68. Public ReadOnly Rand As New Random
      69. Public Function RngBytes(size As Int32) As Byte()
      70. Dim result = New Byte(size - 1) {}
      71. Rand.NextBytes(result)
      72. Return result
      73. End Function
      74. End Module

      Cs - Bitwise Permutation mit Wiederholung Lexikographisch

      C#-Quellcode

      1. //Es handelt sich hier um eine Bitwise Permutation mit Repetition,
      2. //da mehrere 1 oder 0 in der Bit-Repräsentation vorhanden sind.
      3. //Sobald die Zahl 0 (00000000) oder 255 (11111111) ist, wird abgebrochen,
      4. //da man in der Bit-Räpräsentation nur eine sich wiederholende Zahl findet.
      5. //Da die Bitwise PermutationWR lexikographisch erfolgt, muss mit
      6. //einer Startzahl begonnen werden. (N = Anzahl gesetzte Bits)
      7. //Z.B. N = 2 >>> start = 3
      8. //Z.B. N = 3 >>> start = 7
      9. namespace BitwisePermutationTest;
      10. using static RandomHolder;
      11. public class Program
      12. {
      13. public static void Main()
      14. {
      15. TestBitwisePermutationWRLexicoBytes();
      16. Console.ReadLine();
      17. }
      18. private static void TestBitwisePermutationWRLexicoBytes()
      19. {
      20. int k1, i = 1, cnt = byte.MaxValue;
      21. var value = (byte)Rand.Next(256);
      22. //darf nicht 0 oder 255 sein
      23. if (value == 0 || value == 255) PrintOutNoPermutationsWR(value);
      24. if (value > 0 && value < 255)
      25. {
      26. Console.Write(value);
      27. Console.Write($" {Convert.ToString(value, 2)}");
      28. Console.WriteLine($" k1 = {k1 = CountBitsSet(value)}");
      29. Console.WriteLine();
      30. //Da die Bitwise PermutationWR lexikographisch erfolgt,
      31. //muss mit einer Startzahl begonnen werden.
      32. var start = ToStartNumber(k1);
      33. Console.WriteLine($"{start,-4} {Convert.ToString(start, 2)}");
      34. for (i = 1; i < cnt; i++)
      35. {
      36. start = BitwisePermutationWRLexico(start);
      37. if (start == byte.MaxValue) break;
      38. Console.WriteLine($"{start,-4} {Convert.ToString(start, 2)}");
      39. }
      40. }
      41. Console.WriteLine($"count = {i}");
      42. Console.WriteLine();
      43. }
      44. private static void PrintOutNoPermutationsWR(byte value)
      45. {
      46. Console.Write($"One permutations: value = {value} ");
      47. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2)}");
      48. }
      49. private static int CountBitsSet(byte number)
      50. {
      51. //Anzahl der gesetzten Bits in der Zahl.
      52. //http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
      53. int result; // result accumulates the total bits set in v
      54. for (result = 0; number != 0; result++)
      55. // clear the least significant bit set
      56. number = (byte)(number & (number - 1));
      57. return result;
      58. }
      59. private static byte BitwisePermutationWRLexico(byte number)
      60. {
      61. //http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
      62. var t = (byte)((number | (number - 1)) + 1);
      63. return (byte)(t | ((((t & -t) / (number & -number)) >> 1) - 1));
      64. }
      65. private static byte ToStartNumber(int n)
      66. {
      67. var s = new string('1', n);
      68. return Convert.ToByte(s, 2);
      69. }
      70. }
      71. public class RandomHolder
      72. {
      73. public static readonly Random Rand = new();
      74. public static byte[] RngBytes(int size)
      75. {
      76. var result = new byte[size];
      77. Rand.NextBytes(result);
      78. return result;
      79. }
      80. }

      Output

      Quellcode

      1. 176 10110000 k1 = 3
      2. 7 111
      3. 11 1011
      4. 13 1101
      5. 14 1110
      6. 19 10011
      7. 21 10101
      8. 22 10110
      9. 25 11001
      10. 26 11010
      11. 28 11100
      12. 35 100011
      13. 37 100101
      14. 38 100110
      15. 41 101001
      16. 42 101010
      17. 44 101100
      18. 49 110001
      19. 50 110010
      20. 52 110100
      21. 56 111000
      22. 67 1000011
      23. 69 1000101
      24. 70 1000110
      25. 73 1001001
      26. 74 1001010
      27. 76 1001100
      28. 81 1010001
      29. 82 1010010
      30. 84 1010100
      31. 88 1011000
      32. 97 1100001
      33. 98 1100010
      34. 100 1100100
      35. 104 1101000
      36. 112 1110000
      37. 131 10000011
      38. 133 10000101
      39. 134 10000110
      40. 137 10001001
      41. 138 10001010
      42. 140 10001100
      43. 145 10010001
      44. 146 10010010
      45. 148 10010100
      46. 152 10011000
      47. 161 10100001
      48. 162 10100010
      49. 164 10100100
      50. 168 10101000
      51. 176 10110000
      52. 193 11000001
      53. 194 11000010
      54. 196 11000100
      55. 200 11001000
      56. 208 11010000
      57. 224 11100000
      58. count = 56

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „exc-jdbi“ ()

      Bitwise Permutation ohne Wiederholung - Transposition

      Bitwise Permutation ohne Wiederholung - Transposition

      Die Bitwise Permutation ohne Wiederholung arbeitet mit einer Zahl (primitiven Datentype: byte, int32, etc.) und Bitwise-Operationen, daher auch der Name Bitwise.

      Gegeben ist also eine Zahl, z.B. eine Byte Zahl wie 176. Die Bit-Repräsentation ist 10110000. Wie man erkennen kann wiederholen sich die Zahlen (0 und 1) und sind an unterschiedlichen Positionen. Daher kann eine Permutation ohne Wiederholung nur mit einer Transposition realisiert werden, denn eine Permutation ohne Wiederholung erwartet eigentlich eine Menge die keine wiederholende Zahlen hat. Genau aus diesem Grunde wird sie ja auch Permutation OHNE Wiederholung genannt.

      Mit einer Transposition behalten alle Werte in der Menge ihren Wert, dafür aber werden die Positionen umstrukturiert. Bezogen auf die obere Zahl 176 wird man merken, dass viele Zahlen immer wieder sich wiederholen.
      Möchte man keine Wiederholungen der Zahlen in der Ausgabe, so kann das nur mit einer Bitwise Permutation mit Wiederholung gelöst werden. Siehe oberer Artikel Bitwise Permutation mit Wiederholung, Lexikographisch.
      Permutationen

      Eine Transposition oder eine echte Permutation ohne Wiederholung lässt sich mit einer Backtracking realisieren. Es gibt aber auch iterative Funktionen, jedoch wird in den von mir bekannten Möglichkeiten immer eine Werteprüfung gemacht, und somit sind sie keine echte Transpositionen, sondern eher ein Mix von beidem.

      Wie löst man eine Iterative Bitwise Permutation ohne Wiederholung?

      Ein naiver Ansatz wäre das eine Index Array mitgeführt wird. Z.B.

      Quellcode

      1. Index 0 1 2 3 4 5 6 7
      2. Bits 1 0 1 1 0 0 0 0

      Nun ist es möglich die Indexes mit einer iterativen Methode zu lösen, wobei synchron jeweils die Bits mitgeshwapt werden.


      Zeitkomplexität Backtracking (Wikipedia)

      Die Tiefensuche und somit auch Backtracking haben im schlechtesten Fall mit Θ(z^n) und einem Verzweigungsgrad z > 1 eine exponentielle Laufzeit. Je größer die Suchtiefe n, desto länger dauert die Suche nach einer Lösung. Daher ist das Backtracking primär für Probleme mit einem kleinen Lösungsbaum geeignet.


      Anzahl Permutationen

      Die Anzahl der Permutationen lässt sich ganz normal über die Formel für die Permutation ohne Wiederholung berechnen.

      Quellcode

      1. n = 8 * sizeof(T)
      2. nop = Number of Permutation
      3. nop = n!


      Werkzeuge für die Berechnung der Anzahl Permutationen

      VB.NET-Quellcode

      1. Private Function Factorial(number As UInt64) As UInt64
      2. Dim result As UInt64 = 1
      3. If number = 0 OrElse number = 1 Then
      4. result = 1
      5. Else
      6. For i As UInt64 = 1 To number
      7. result *= i
      8. Next
      9. End If
      10. Return result
      11. End Function

      C#-Quellcode

      1. private static ulong Factorial(ulong number)
      2. {
      3. ulong result = 1;
      4. if (number == 0 || number == 1)
      5. result = 1;
      6. else
      7. for (ulong i = 1; i <= number; i++)
      8. result *= i;
      9. return result;
      10. }


      Wer sich weiter informieren will, hier noch ein paar Links.
      de.wikipedia.org/wiki/Transposition_(Kryptographie)
      de.wikipedia.org/wiki/Permutat…utation_ohne_Wiederholung
      de.wikipedia.org/wiki/Backtracking

      Und auch hier zuletzt noch der Code. Es ist auch eine Byte Variante. Alle Funktionen können natürlich für andere primitive Datentypen umgeändert werden. Beachtet jedoch, dass es bei einem Datentype ui16 doch schon 2.09228E13 Permutationen sind.

      Freundliche Grüsse

      exc-jdbi

      Vb.Net - Bitwise Permutation ohne Wiederholung - Transposition

      VB.NET-Quellcode

      1. Namespace BitwisePermutationTest
      2. Public Module Program2
      3. Public Sub Main()
      4. TestBitwisePermutationWOR_Trasposition()
      5. Console.ReadLine()
      6. End Sub
      7. Private Sub TestBitwisePermutationWOR_Trasposition()
      8. Dim count = 1UL
      9. Dim value = Convert.ToByte(Rand.[Next](256))
      10. 'hier ohne 0 oder 255
      11. If value = 0 OrElse value = 255 Then PrintOutNoPermutationsWR(value)
      12. If value > 0 AndAlso value < 255 Then
      13. Console.Write(value)
      14. Console.WriteLine($" {Convert.ToString(value, 2)}")
      15. Console.WriteLine()
      16. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2).PadLeft(8, "0"c)}")
      17. Dim n = 8
      18. count = 0UL
      19. Dim result = value
      20. BitwisePermutationWOR_Transposition(result, 0, n, count)
      21. End If
      22. Console.WriteLine($"count = {count}")
      23. Console.WriteLine()
      24. End Sub
      25. Private Sub PrintOutNoPermutationsWR(value As Byte)
      26. Console.Write($"One permutations: value = {value} ")
      27. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2)}")
      28. End Sub
      29. Private Sub BitwisePermutationWOR_Transposition(ByRef input As Byte, s As Int32, e As Int32, ByRef count As UInt64)
      30. 'Without Repetition - Transposition - LastBegin - Recursiv
      31. If s = e Then
      32. count += 1
      33. Console.WriteLine($"{input,-4} {Convert.ToString(input, 2).PadLeft(8, "0"c)}")
      34. Return
      35. End If
      36. For j = s To e - 1
      37. SwapBits(input, s, j)
      38. BitwisePermutationWOR_Transposition(input, s + 1, e, count)
      39. SwapBits(input, s, j)
      40. Next
      41. End Sub
      42. Private Sub SwapBits(ByRef number As Byte, i As Int32, j As Int32)
      43. Dim x = (number >> i Xor number >> j) And 1
      44. number = number Xor x << i Or x << j
      45. End Sub
      46. End Module
      47. End Namespace

      Cs - Bitwise Permutation ohne Wiederholung - Transposition

      C#-Quellcode

      1. namespace BitwisePermutationTest;
      2. using static RandomHolder;
      3. public class Program2
      4. {
      5. public static void Main()
      6. {
      7. TestBitwisePermutationWOR_Trasposition();
      8. Console.ReadLine();
      9. }
      10. private static void TestBitwisePermutationWOR_Trasposition()
      11. {
      12. var count = 1ul;
      13. var value = (byte)Rand.Next(256);
      14. //hier ohne 0 oder 255
      15. if (value == 0 || value == 255) PrintOutNoPermutationsWR(value);
      16. if (value > 0 && value < 255)
      17. {
      18. Console.Write(value);
      19. Console.WriteLine($" {Convert.ToString(value, 2)}");
      20. Console.WriteLine();
      21. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2).PadLeft(8, '0')}");
      22. var n = 8 * sizeof(byte);
      23. var result = value;
      24. count = 0ul;
      25. BitwisePermutationWOR_Transposition(ref result,0, n, ref count);
      26. }
      27. Console.WriteLine($"count = {count}");
      28. Console.WriteLine();
      29. }
      30. private static void PrintOutNoPermutationsWR(byte value)
      31. {
      32. Console.Write($"One permutations: value = {value} ");
      33. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2)}");
      34. }
      35. private static void BitwisePermutationWOR_Transposition(ref byte input, int s, int e, ref ulong count)
      36. {
      37. //Without Repetition - Transposition - LastBegin - Recursiv
      38. if (s == e)
      39. {
      40. count++;
      41. Console.WriteLine($"{input,-4} {Convert.ToString(input, 2).PadLeft(8, '0')}");
      42. return;
      43. }
      44. for (int j = s; j < e; j++)
      45. {
      46. SwapBits(ref input, s, j);
      47. BitwisePermutationWOR_Transposition(ref input, s + 1, e, ref count);
      48. SwapBits(ref input, s, j);
      49. }
      50. }
      51. private static void SwapBits(ref byte number, int i, int j)
      52. {
      53. byte x = (byte)(((number >> i) ^ (number >> j)) & 1);
      54. number = (byte)(number ^ ((x << i) | (x << j)));
      55. }
      56. }

      Output

      Quellcode

      1. 176 10110000
      2. 176 10110000
      3. 176 10110000
      4. 112 01110000
      5. 208 11010000
      6. 208 11010000
      7. 176 10110000
      8. 112 01110000
      9. 176 10110000
      10. 112 01110000
      11. 208 11010000
      12. 208 11010000
      13. 176 10110000
      14. 112 01110000
      15. 224 11100000
      16. 224 11100000
      17. 224 11100000
      18. 224 11100000
      19. 224 11100000
      20. 224 11100000
      21. ...
      22. ...
      23. ...
      24. 81 01010001
      25. 145 10010001
      26. 145 10010001
      27. 81 01010001
      28. 97 01100001
      29. 161 10100001
      30. 97 01100001
      31. 161 10100001
      32. 193 11000001
      33. 193 11000001
      34. 161 10100001
      35. 97 01100001
      36. 193 11000001
      37. 193 11000001
      38. 161 10100001
      39. 97 01100001
      40. count = 40320

      Dieser Beitrag wurde bereits 7 mal editiert, zuletzt von „exc-jdbi“ ()

      exc-jdbi schrieb:

      Daher kann eine Permutation ohne Wiederholung nur mit einer Transposition realisiert werden, denn eine Permutation ohne Wiederholung erwartet eigentlich eine Menge die keine wiederholende Zahlen hat.
      Ja, das ist scheinbar ein Paradoxon - hat aber eine Standard-Lösung.
      In codeproject.com/Articles/1111639/Permutations-2, Abschnitt "The special and the very special case" spreche ich das an.
      Und in Abschnitt "Lexicographic Permutation as described by Dijkstra" zeige ich eine Implementierung der (lexicografischen) Lösung, die ein gewisser Herr Dijkstra gefunden hat.
      Damit kann man alle möglichen Arrays ohne Wiederholung permutieren, auch wenn das Ausgangss-Array Wiederholungen enthält.
      Also auch ein Bool-Array kann man damit durchnibbeln, ohne dass Dubletten überhaupt entstünden, und man erhielte dieselben Ergebnisse wie mit deim Algorithmus.

      Ich habe nicht den mathematischen Begriff dieser kombinatorischen Operation gefunden - nennt man das "Transposition"?
      Jo die Seite werde ich mir schon mal anschauen müsse, und werde dann auch das Projekt runterladen.

      Ich habe schon von Dijkstra gelesen, ist mir aber jetzt nicht gerade present, was man alles damit machen kann. Werde ich auch anschauen.

      Leider weiss ich den genauen Fachbegriff für so was nicht, ich musste einfach einen Ansatz bringen, damit ich es besser erklären konnte. Auch der Begriff Transposition hat sich in den letzten Jahren auf Wikipedia geändert. Früher meinte man damit das austauschen von 2 Objekten, z.B. das swapen. Heute wird es viel umfangreicher verwendet, darum verwende ich diesen Begriff auch so gerne.

      Freundliche Grüsse

      exc-jdbi

      Cs - Bitwise Permutation ohne Wiederholung - Iterativ - Dijkstra

      C#-Quellcode

      1. namespace DijkstraAlgorithmTest;
      2. using static RandomHolder;
      3. public class DijkstraPermutation
      4. {
      5. public static void Main()
      6. {
      7. TestDijkstra();
      8. Console.ReadLine();
      9. }
      10. private static void TestDijkstra()
      11. {
      12. var count = 0;
      13. var value = (byte)Rand.Next(256);
      14. Console.WriteLine($"{value,-4} {Convert.ToString(value, 2).PadLeft(8, '0')}");
      15. Console.WriteLine();
      16. foreach (var number in PermuteDijkstra(value))
      17. {
      18. count++;
      19. if (count <= 362880)
      20. Console.WriteLine($"{number,-4} {Convert.ToString(number, 2).PadLeft(8, '0')}");
      21. else break;
      22. }
      23. Console.WriteLine($"count = {count}");
      24. Console.WriteLine($"number = {value,-4} {Convert.ToString(value, 2).PadLeft(8, '0')}");
      25. }
      26. private static IEnumerable<byte> PermuteDijkstra(byte number)
      27. {
      28. //Damit das funktioniert, wird ein Indexer mitgeführt.
      29. //in dem Sinne handelt es sich um eine naive
      30. var bitsize = 8 * sizeof(byte);
      31. var index = Enumerable.Range(0, bitsize).ToArray();
      32. yield return number;
      33. while (true)
      34. {
      35. int x = bitsize - 2;
      36. while (x >= 0 && index[x] >= index[x + 1])
      37. --x;
      38. if (x < 0) yield break;
      39. int y = bitsize - 1;
      40. while (y > x && index[x] >= index[y])
      41. y--;
      42. Swap(ref index[x], ref index[y]);
      43. SwapBits(ref number, -x - 1 + bitsize, -y - 1 + bitsize);
      44. Array.Reverse(index, x + 1, bitsize - x - 1);
      45. yield return number = ReversBitN(number, 0, bitsize - x - 1);
      46. }
      47. }
      48. private static byte ReversBitN(byte number, int start, int count)
      49. {
      50. if (count < 2) return number;
      51. var c = count / 2;
      52. var h = start + count - 1;
      53. for (var i = 0; i < c; i++)
      54. SwapBits(ref number, h--, start++);
      55. return number;
      56. }
      57. private static void Swap<T>(ref T x, ref T y)
      58. => (y, x) = (x, y);
      59. private static void SwapBits(ref byte number, int i, int j)
      60. {
      61. byte x = (byte)(((number >> i) ^ (number >> j)) & 1);
      62. number = (byte)(number ^ ((x << i) | (x << j)));
      63. }
      64. }
      65. public class RandomHolder
      66. {
      67. public static readonly Random Rand = new();
      68. }

      Cs - Bitwise Permutation ohne Wiederholung - Iterativ - Mal ganz anders

      C#-Quellcode

      1. //Für die Permutation ohne Wiederholung, jedoch mit einer
      2. //Menge die wiederholende Zahlen hat, habe ich zuerst die
      3. //Permutation mit Wiederholung genommen, damit ich die Liste
      4. //bekomme mit allen Möglichkeiten. Mit den Coprimes der Länge
      5. //der Liste kann dann der Ablauf gesteuert werden, wie die einzelnen
      6. //Möglichkeiten in der Liste gesamthaft ausgegeben werden sollen.
      7. //Simpel und einfach, aber genau das, was die Permutation ohne
      8. //Wiederholung mit einer Menge in der wiederholende Zahlen
      9. //vorkommen machen muss.
      10. using System.IO;
      11. using System.Diagnostics;
      12. namespace BitwisePermutationTest;
      13. using static RandomHolder;
      14. public class TestPermuteByteWOR
      15. {
      16. public static void Main()
      17. {
      18. TestPermuteWithoutRepetitionSpec();
      19. Console.ReadLine();
      20. }
      21. private static void TestPermuteWithoutRepetitionSpec()
      22. {
      23. var number = (byte)Rand.Next(256);
      24. var nopwor = Factorial(8* sizeof(byte));
      25. var nopwr = ToNumberOfPermutation(number, 8);
      26. var plist = ToBitwisePermutationWRLexicoBytes(number);
      27. if (nopwr != (ulong)plist.Length)
      28. throw new ArgumentNullException(nameof(number));
      29. byte n;
      30. int counter = 0, offset = 0;
      31. var rounds = (int)(nopwor / nopwr) - 1;
      32. var coprimes = ToCoprimes(plist.Length);
      33. for (var i = 0; i < plist.Length; i++)
      34. {
      35. n = plist[i];
      36. Console.WriteLine($"{n,-4} {Convert.ToString(n, 2)}");
      37. counter++;
      38. }
      39. for (var i = 0; i < rounds; i++)
      40. {
      41. if (i > 0 && i % coprimes.Length == 0) offset++;
      42. for (var j = 0; j < plist.Length; j++)
      43. {
      44. n = plist[((j * coprimes[i % coprimes.Length]) + offset) % plist.Length];
      45. Console.WriteLine($"{n,-4} {Convert.ToString(n, 2)}");
      46. counter++;
      47. }
      48. }
      49. Console.WriteLine($"count = {counter}");
      50. Console.WriteLine();
      51. }
      52. private static byte[] ToBitwisePermutationWRLexicoBytes(byte number)
      53. {
      54. var cnt = byte.MaxValue;
      55. var k1 = CountBitsSet(number);
      56. var start = ToStartNumber(k1);
      57. var result = new List<byte>() { start};
      58. for (var i = 1; i < cnt; i++)
      59. {
      60. start = BitwisePermutationWRLexico(start);
      61. if (start == byte.MaxValue) break;
      62. result.Add(start);
      63. }
      64. return result.ToArray();
      65. }
      66. private static int CountBitsSet(byte number)
      67. {
      68. //Anzahl der gesetzten Bits in der Zahl.
      69. //http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan
      70. int result; // result accumulates the total bits set in v
      71. for (result = 0; number != 0; result++)
      72. // clear the least significant bit set
      73. number = (byte)(number & (number - 1));
      74. return result;
      75. }
      76. private static byte BitwisePermutationWRLexico(byte number)
      77. {
      78. //http://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
      79. var t = (byte)((number | (number - 1)) + 1);
      80. return (byte)(t | ((((t & -t) / (number & -number)) >> 1) - 1));
      81. }
      82. private static byte ToStartNumber(int n)
      83. => (byte)(Math.Pow(2, n) - 1);
      84. private static uint ToNumberOfPermutation(uint number, int size)
      85. {
      86. var k1 = CountBitsSet((byte)number);
      87. var k0 = size - k1;
      88. ulong result = Factorial((ulong)size);
      89. result /= Factorial((ulong)k0);
      90. result /= Factorial((ulong)k1);
      91. return (uint)result;
      92. }
      93. private static ulong Factorial(ulong number)
      94. {
      95. ulong result = 1;
      96. if (number == 0 || number == 1)
      97. result = 1;
      98. else
      99. for (ulong i = 1; i <= number; i++)
      100. result *= i;
      101. return result;
      102. }
      103. private static int[] ToCoprimes(int number)
      104. {
      105. var start = 2;
      106. var result = new List<int>();
      107. for (var i = 2; i < number; i++)
      108. if (Gcd(start++, number) == 1)
      109. result.Add(start - 1);
      110. return result.ToArray();
      111. }
      112. private static int Gcd(int A, int B)
      113. {
      114. if (B != 0) return Gcd(B, A % B);
      115. return A;
      116. }
      117. }

      Dieser Beitrag wurde bereits 5 mal editiert, zuletzt von „exc-jdbi“ ()