"ABCD" in allen möglichen Kombinationen

[3_of_8]

Er spricht von einer simplem Permutation.

Achja, dazu gibt es CodeLib-Einträge.

Permutation

[-lx-]

Hallo,


also mir ist das Prinzip von dino noch immer nicht klar.

A B C D
A B D C
A C B D <--- wieso ? Wieso nicht A D B C ?



also mir ist der Mechanismus noch nicht klar, wie man man denn beim Vertauschen vor geht. Man kann doch nicht einfach willkürlich tauschen. Es müsste ja eig. immer schrittweise gehen - rekursiv eben.

[dino]

Zitat von -lx-:

A B C D
A B D C
A C B D <--- wieso ? Wieso nicht A D B C ?

weil ich von links nach recht immer den kleinstmöglichsten Buchstaben nehme, dessen Kombination nch nicht vorgekommen ist

[alzaimar]

Also, ich habe eine Liste, die ich in allen möglichen Kombinationen zusammenstellen will.
Na denn:

Code:

Erzeuge alle Permutationen (Liste L, bisherige Lösung)
Für jedes Element E in der Liste L
  Wenn E noch nicht in der bisherigen Lösung enthalten ist, dann
      Wenn E das letzte noch nicht verwendete Element der Liste ist, dann
         Ist [Lösung + E] eine Permutation
      ansonsten
         Erzeuge alle Permutationen (L, Lösung + E)

Das ist übrigens schon fast die fertige rekursive Routine. Wenn Du das verstanden hast, kannst du es auch implementieren.

[-lx-]

Hab heute den Vater meiner Freundinn auch nochmal gefragt, wie man denn sowas anpackt. Und er hat es mir auch so erklärt, wie Dino es angesprochen hat.

Nur hab ich es bei ihm besser verstanden. Warscheinlich weil eien direkte Konversation mehr bringt als was geschriebenes. Nichst gegen euch =)


Ich danke euch für eure mühen. Ihr werden in den nächsten Postings dann meien Programmieransätze sehen !




mit freundlichen Grüßen

[Cöster]

Das hat mir jetzt keine Ruhe gelassen

Hier mein Quellcode:

Delphi-Quellcode:

function TForm1.Factorial(const x: Byte): Word;
begin
  if x > 1 then
    result := x * Factorial(x - 1)
  else
    result := x;
end;

procedure TForm1.CalcNextS(var s: string; const Initial: string);
var
  l: Byte; // Position linker Austauschpartner
  r: Byte; // Position rechter Austauschpartner
  i: Byte; // Laufvariable
  Done: Boolean; // für Bubblesort
  Temp: Char;
begin

  // linken Austauschpartner finden
  l := Length(s);
  repeat
    Dec(l);
  until Pos(s[l], Initial) < Pos(s[l+1], Initial);

  // rechten Austauschpartner finden
  r := l + 1;
  for i := l to Length(s) do
    if (Pos(s[i], Initial) > Pos(s[l], Initial)) and
      (Pos(s[i], Initial) < Pos(s[r], Initial)) then
        r := i;

  // austauschen
  Temp := s[l];
  s[l] := s[r];
  s[r] := Temp;

  // rechts von l der Größe nach sortieren
  if l <> Length(s) - 1 then
    repeat
      Done := True;
      for i := l+1 to Length(s) - 1 do
        if Pos(s[i], Initial) > Pos(s[i+1], Initial) then
        begin
          Temp := s[i];
          s[i] := s[i+1];
          s[i+1] := Temp;
          Done := False;
        end;
    until Done;

end;

procedure TForm1.Button1Click(Sender: TObject);
var
  i: Integer;
  s: string;
begin
  ListBox1.Clear;
  s := Edit1.Text;
  ListBox1.Items.Add(s);
  for i := 2 to Factorial(Length(s)) do
  begin
    CalcNextS(s, Edit1.Text);
    ListBox1.Items.Add(s);
  end;
end;

Das Wort kann aus bis zu 255 Zeichen bestehen. Ich hab allerdings noch nicht berücksichtigt, dass Buchstaben auch mehrfach vorkommen können.

Die .exe ist im Anhang

[Cöster]

Zitat von Cöster:

Das Wort kann aus bis zu 255 Zeichen bestehen. Ich hab allerdings noch nicht berücksichtigt, dass Buchstaben auch mehrfach vorkommen können.

Äh, nee, kann doch nur aus 12 Buchstaben/Zahlen bestehen, weil die Fakultät sonst nicht mehr in den Integerrahmen passt. Es braucht bei 8 Zeichen aber auch schon ca. 6 Sekunden, bei 9 über ner Minute, ein Progressbar wär wohl angebracht.

Dass Zeichen sich wiederholen können, hab ich jetzt auch gelöst: Bevor nach Kombinationen gesucht wird, werden die Zeichen sortiert. Pro Zeichen, welches x-mal hintereinander vorkommt, wird die Anzahl der Kombinationen dann durch x! geteilt.

[3_of_8]

Genaugenommen kann ein String theoretisch bis zu 2 (oder warens 4) GiB groß sein.

[dino]

meins ist zwar nur für 7 Zeichen, aber ungefähr gleich schnell

[Cöster]

Zitat von 3_of_8:

Genaugenommen kann ein String theoretisch bis zu 2 (oder warens 4) GiB groß sein.

Ja, aber wenn der String aus 13 verschiedenen Zeichen besteht, gibt es 13!, also 6227020800, Kombinationsmöglichkeiten. Das ist für die ListBox zu viel, die Funktion Factorioal geht auch nur bis zur Integergrenze und außerdem würde die Berechnung über 2 Wochen dauern. Bei 12 Zeichen würde es wahrscheinlich "nur" knapp über einem Tag dauern und die beiden anderen Probleme gäb's auch nicht.