Entwickler-Ecke :: Thema anzeigen - Algorithmus zum Finden von Buchstabenkombinationen

bfelix - Di 22.03.11 17:00
Titel: Algorithmus zum Finden von Buchstabenkombinationen

Hallo Community,
ich würde gerne einen Algorithmus machen, der alle Buchstaben Kombinationen aus einem bestimmten Vorratsstring mit einer bestimmten Länge findet. Mein Ansatz:
1. Length(vorrat)^(Anzahl Buchstaben-1) mal die Zeichen von vorrat hintereinanderschreiben in TStrings: (dabei hoch eine eigene Funktion zur Potenz, vorrat der Vorratsstring und laenge die Länge der Ausgabestrings)

Delphi-Quelltext

1:
2:
3:
4:
5:

for i:=0 to hoch(Length(vorrat,laenge-1)) do begin
  for j:=1 to Length(vorrat) do begin
    strs.Items.Add(vorrat[j]);
  end;
end;

2. Weiter fällt mir leider nichts ein...

Kann mir irgendwer wenigstens einen Ansatz geben?

Danke im Vorraus,
BFelix

Delete - Di 22.03.11 17:25

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:

function MaxKombinations(Len: integer; const Chars: string): Int64;
var
  Factor            : Int64;
begin
  Result := 0;
  Factor := 1;
  while Len > 0 do
  begin
    dec(Len);
    Result := Result + Factor;
    Factor := Factor * Length(Chars);
  end;
end;

function BruteForce(Nb: Int64; Chars: string): string;
begin
  Result := '';
  while Nb > Length(Chars) do
  begin
    dec(Nb);
    Result := Chars[Nb mod Length(Chars) + 1] + Result;
    Nb := Nb div Length(Chars);
  end;
  if Nb > 0 then
    Result := Chars[Nb] + Result;
end;

Aufruf mit:

Delphi-Quelltext

1:
2:
3:
4:

MaxChars := MaxKombinations(MinLen, Chars);
  while (length(s) <= Maxlen) and (not Terminate) do
  begin
    s := BruteForce(MaxChars, Chars);

bfelix - Di 22.03.11 17:56

Gut, ich habe jetzt noch einen Ansatz:

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:

for i:=1 to Length(vorrat) do begin
  for j:=1 to Length(vorrat) do begin
    for u:=1 to Length(vorrat) do begin
      for m:=1 to Length(vorrat) do begin
        erg:='';
        erg:=erg+vorrat[i];
        erg:=erg+vorrat[j];
        erg:=erg+vorrat[u];
        erg:=erg+vorrat[m];
        erg1.Add(erg);
      end;
    end;
  end;
end;

Dabei ist erg ein String und erg1 eine Stringliste für das Ergebnis
Es bibt dann ja eine Liste mit allen Kombinationen mit 4 Buchstaben aus.
Aber wie kann ich das so in einer Schleife verpacken, dass es alle Kombinationen mit der Länge x ausgibt??

Danke,
BFelix

Chrischuh - Di 22.03.11 18:55

Delphi-Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure Kombinationen(Vorrat: string; laenge: Integer; Zwischenspeicher: string; Liste: TStrings);
var i:integer;s:string;
begin
   dec(laenge);
   for i := 1 to length(vorrat) do
   begin
     s:=Zwischenspeicher + Vorrat[i];
     if laenge>0 then Kombinationen(vorrat,laenge, s, liste) else
     liste.Add(s);

   end;

end;

Das ist die Prozedur. Hoffe das ist so richtig.
So ist der Aufruf:

Delphi-Quelltext

1:
2:
3:
4:
5:

procedure TForm1.Button1Click(Sender: TObject);
begin
memo1.Lines.Clear;
Kombinationen(edit1.Text,4,'',Memo1.Lines);
end;

bzw

Delphi-Quelltext

1:	Kombinationen(Vorratsstring,Maximale_länge,'',Ziel_TStrings);

Hoffe das ist das was du suchst.

Es wird jedes mögliche zeichen an den Anfang gesetzt. Und dann wird die Funktion einfach solange erneut aufgerufen, bis die strings lang genug sind.

Entwickler-Ecke.de based on phpBB
Copyright 2002 - 2011 by Tino Teuber, Copyright 2011 - 2025 by Christian Stelzmann Alle Rechte vorbehalten.
Alle Beiträge stammen von dritten Personen und dürfen geltendes Recht nicht verletzen.
Entwickler-Ecke und die zugehörigen Webseiten distanzieren sich ausdrücklich von Fremdinhalten jeglicher Art!