Hi marabu,
die hier ist nett:
Delphi-Quellcode:
Function NthPermutation (const aString : AnsiString; aCount : Cardinal) : String;
Var
pos, i, n : Cardinal;
c : char;
Begin
n := Length(aString);
result := aString;
for i := n downto 2 do begin
pos := acount mod i +1;
c := result[i];
result[i] := result[Pos];
result[Pos] := c;
acount := acount div i;
End;
End;
Sie (die Funktion, oder Er, der Algorithmus) erzeugt direkt die n.te Permutation einer Zeichenkette mit x Buchstaben (n=0..x!-1). Sie mischt die Eingabezeichenfolge einfach in einer wohldefinierten Form, herrlich!
Ich habe noch Einen: Permutationen ordnen, die Ordnungszahl in eine Zahl mit variabler Basis umwandeln, davon die Inverse (das sind Graycodes) und das dann umgekehrt implementieren, ergibt einen ziemlich perversen Algorithmus.
Hier die Herleitung:
Man kann Permutationen aufzählen. Dazu schreibt man alle Permutationen auf. Anschließend schreibt man neben jede Permutation den Inverse-Code: Für jedes Zeichen wird die Anzahl der Zeichen gezählt, die rechts vom Zeichen vorkommen und größer sind.
Jede Stelle i (1..n) dieses Codes wird nun mit (i-1)! multipliziert (von rechts zählen). Wir erhalten die Zahlen von 0 bis n!-1 (n=Anzahl der Stellen). Damit haben wir eine Ordnung auf den Permutationen und können auch die 519.te Permutation ermitteln.
- 321 000 0
312 010 1
231 100 2
213 110 3
132 200 4
123 210 5
Hier der Algorithmus
Delphi-Quellcode:
Function NthPermutationViaInverse (aString : String; aCount : Integer) : String;
Var
d : Array Of Integer;
g, i, n : Integer;
Begin
n := Length (aString);
setlength (d, n);
d[1] := 1;
For i := 2 to n - 1 do d[i] := i * d[i-1];
Result := '';
for i := n-1 downto 1 do begin
g := (aCount div d[i]) + 1;
Result := Result + aString[g];
delete (aString, g, 1);
aCount := aCount mod d[i];
End;
Result := Result + aString;
End;