Komplette Kombinationsmöglichkeiten einer Zahl ausgeben

[alzaimar]

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;