Komplette Kombinationsmöglichkeiten einer Zahl ausgeben

[wursthunter]

Ich habe eine Zahl die aus x Zahlen besteht. Keiner dieser Ziffern is doppelt!

Bespiel: 123

Ausgabe( 123, 132, 312, 321, 231, 213)

Aber das ganze wird 4, 5, 6 oder mehr zahlen schon komplizierter!

Wie bekomm ich nun alles in einen schönen Algorhitmus?

[flowoeB]

hi!

schreit nach einem recursiven algorithmus. ist die einfachste moeglichkeit. laesst sich aber auch ueber dancing links loesen (wahrscheinlich die schnellste methode) ( siehe Dancing Links )

MfG Flo

[Flare]

Also ich habe mir den Text mal durchgelesen (Dancing Links) und ich muss sagen, dass ich damit recht wenig anfangen kann, könntest du das vielleicht auf deutsch erklären? Diese Frage interessiert mich nämlich auch


Flare

[flowoeB]

hi!

das ganze zu uebersetzten ueberschreitet sowohl meine zeit wie auch meinen englischwortschatz
nach dem text DLX zu verstehen ist auch imho nicht recht einfach. mir hat das hier (am beispiel sudoku): klick mich sehr weitergeholfen. es gibt auch etliche implementationen im netz die sich zu studieren lohnen.

MfG Flo

[marabu]

Ich habe es immer als ein Permutationsproblem verstanden. Hier ein modernisierter TP1 Code zum Erstellen aller Kombinationen n aus m:

Delphi-Quellcode:

procedure Permute(Head, Tail: String; s: TStrings; const size: Integer);
var
  i: Integer;
  Newhead, Newtail: String;
begin
  for i := 1 to Length(Tail) do
  begin
    Newhead := Head + Tail[i];
    Newtail := Tail;
    Delete(NewTail, i, 1);
    if (Newtail = '') or (Length(Newhead) = size)
      then s.Add(NewHead)
      else Permute(Newhead, Newtail, s, size);
  end;
end;

Der passende Aufruf zu deinem Beispiel:

Delphi-Quellcode:

begin
  sNumber := '123';
  s := TStringList.Create;
  Permute('', sNumber, s, Length(sNumber));
  WriteLn(s.Text);
  s.Free;
end;

Hier in der DP habe ich auch schon nicht-rekursive Lösungen gesehen.

Grüße vom marabu

[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;

[marabu]

Hallo alzaimar,

drei zwei eins - und meins - wenn du nichts dagegen hast. Wer weiß wofür ich das mal brauchen kann.

Grüße vom marabu

[Luckie]

Das ist gut, dann kann man ja bei einem BruteForce sagen, ich will da und da anfangen. Das könnte ich bei meinem PasswordRecover benutzen, um irgendwo zu unterbrechen und dort später dann weitermachen. Das muss ich mir noch mal durch den Kopf gehen lassen.

Nur wie bekommt man die Gesamtzahl aller Möglichkeiten raus?

[alzaimar]

@marabu: Bedien Dich!
@Luckie: n! (n=Anzahl der Stellen)
Beweis:
IA. Bei einer Stelle gibt es eine Möglichkleit (q.e.d)
IB. Bei n-1 Stellen gibt es (n-1)! Möglichkeiten. (unbewiesen, aber Annahme)
IS. Nehme ich eine Stelle hinzu, kann ich die an jeder der n Stellen der bisherigen Kombinationen einfügen. Das ergibt summa summarum n* [(n-1)!] = n! Möglichkeiten. (q.e.d)

[Luckie]

Unter der Annahme, dass ein Zeichen nur einmal vorkommen kann und auch mindestens einmal vorkommen muss. Also wäre 322 eine ungültige Kombination.