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: 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: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: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: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:

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)
   

Ausgabe:
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:

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

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:

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: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:

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"?