Bruteforce Algorithmus

[Luckie]

Ich habe folgenden Bruteforce Algorithmus:

Delphi-Quellcode:

function BruteForceLengthIndex(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;

procedure TForm1.Button1Click(Sender: TObject);
const
  CHARS = 'abcdefghijklmnopqrstuvwxyz';
var
  MaxChars: Int64;
  s: string;
begin
  MaxChars := BruteForceLengthIndex(3, CHARS);
  while (length(s) <= 3) do
  begin
    s := BruteForce(MaxChars, CHARS);
    Caption := s;
    if s = 'zzzz' then
      exit;
    Inc(MaxChars);
  end;
end;

Dazu hab eich folgende Fragen:
1. Was macht BruteForceLengthIndex und wozu wird diese Funktion benötigt?
2. Wenn ich drei angebe, bildet er trotzdem alle Kombinationen mit vier Stellen durch. Was stimmt da nicht?
3. Er findet die Kombination "zzzz" nicht (aber "zzz"), obwohl er trotz der Länge von drei auch alle Kombinationen mit vier Stellen durchprobiert.
Muss mich wohl korrigieren. Er zeigt nur "aaaa" an, wenn er alle Kombinationen durch hat.

Ich bräuchte einen Algorithmus bei dem ich die minimale Anzahl Stellen und die maximale Anzahl Stellen angebe. Also wenn min=3 und max=5 ist, soll er bei "aaa" anfangen und bei "zzzzz" enden.

Ich nehme alles zurück und behaupte das Gegenteil. Bleibt nur Frage eins.

Und noch was, wie kann ich da eine Fortschrittsanzeige mitlaufen lassen?

[sx2008]

Zitat:

Zitat von Luckie (Beitrag 1060491)

Was macht BruteForceLengthIndex und wozu wird diese Funktion benötigt?

Es wird die Anzahl aller möglichen Kombinationen berechnet.
Mathematisch wäre das AnzahlZeichen ^ Länge.
Könnte man auch so rechnen:

Delphi-Quellcode:

Result := IntPower(Length(chars), len);

[Assarbad]

Wie? Du hast ne Funktion und weißt nicht was sie macht? Du hast doch vermutlich dennoch mehr Kontext als wir, oder?

Zitat:

Zitat von Luckie (Beitrag 1060491)

Dazu hab eich folgende Fragen:
1. Was macht BruteForceLengthIndex und wozu wird diese Funktion benötigt?

Sieht für mich ganz danach aus, als könne man den zurückgegebenen Wert auch dazu verwenden zu reproduzieren welche Kombination getestet wurde.

Die Edith: Warnung vor fremder Antwort funzte nich :mrgreen:
Edith die Zweite: meines Erachtens nach würde die Verwendung von ShortString (natürlich unter der Annahme daß die Maximallänge auf 255 begrenzt wird) deutlich flotter gehen.

[Luckie]

@Oliver: Der Code ist schon mehrere Jahre alt. ;)

[himitsu]

Mit BruteForceLengthIndex kann man ausrechnen, welchen Berechnungsindex die erste Kombination mit n Stellen besitzt.
Wie schon gesagt, hätte man das auch mathematisch und ohne Schleife "errechnen" können. :stupid:

Bei dir wurde damit also der Index berechnent, über welchen dann bei BruteForce 'aaa' rauskommt.

Und nein, es werden nicht alle Werte für 3 und 4 Stellen berechnet, sondern nur noch der erste 4-Stellige.
Für 3 Stellen hätte also

Delphi-Quellcode:

if s = 'aaaa' then exit;

grad noch so geklappt.

Vielleicht sieht es so besser/übersichtlicher aus?

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
const
  CHARS = 'abcdefghijklmnopqrstuvwxyz';
  TEST = 'zzz';
var
  Index, Stop: Int64;
  s: string;
begin
  Index := BruteForceLengthIndex(Length(TEST), CHARS);
  Stop := BruteForceLengthIndex(Length(TEST) + 1, CHARS) - 1;
  while Index <= Stop do
  begin
    s := BruteForce(Index, CHARS);
    Caption := s;
    if s = TEST then
      break;
    Inc(Index);
  end;
end;

oder

Delphi-Quellcode:

procedure TForm1.Button1Click(Sender: TObject);
const
  CHARS = 'abcdefghijklmnopqrstuvwxyz';
  TEST = 'zzz';
var
  Start, Stop, Index: Int64;
  s: string;
begin
  Start := BruteForceLengthIndex(Length(TEST), CHARS);
  Stop := BruteForceLengthIndex(Length(TEST) + 1, CHARS) - 1;
  Index := Start;
  while Index <= Stop do
  begin
    s := BruteForce(Index, CHARS);
    Caption := Format('%s (%.1n%%)', [s, (Index - Start) / (Stop - Start) * 100]);
    if s = TEST then
      break;
    Inc(Index);
  end;
end;

Und um bei Olli mitzumachen:
Och, auch mit Ansi könnte es schön schnell sein,
vorallem wenn man nicht ständig den ganzen String komplett neu zusammenstellt, sondern nur die relevanten Teile ändert.

PS: Über den AnsiString als Result muß nur ein Zeiger kopiert und die Referenzzählung angepaßt werden, wärend beim ShortString der komplette Record/String kopiert werden muß.
Als Var-Parameter, anstatt als Result, wär's bestimmt schneller, wärend die zuvielen

Delphi-Quellcode:

Result := Chars[...] + Result;

als

Delphi-Quellcode:

SetLength(Result, Len);

und

Delphi-Quellcode:

Result[i] := Chars[...];

sowieso viel ersparen würde. :angle2:

[Luckie]

Also wäre der BruteForce Algorithmus noch optimierbar? Ich weiß nicht, ob das bei mir was bringt, denn der Flaschenhals liegt an anderer Stelle, auf die ich keinen Einfluss habe.

Ich habe die Funktion jetzt in MaxKombinations umbenannt.

[SirThornberry]

Also wenn du kein Moderator wärest wäre ich jetzt besorgt das du mit solchen Funktionen hantierst und hier bei der Frage nicht angibst wofür du das ganze benötigst. Denn du weißt ja - manchmal gibt es auch eine bessere/sinnvollere Variante wenn man denn nur den eigentlichen Verwendungszweck kennt.

[Luckie]

Ja, verstehe ich. Aber genau deswegen bin ich etwas zurückhaltend mit Informationen, weil ich mir selbst noch nicht sicher bin, ob ich das Resultat groß bewerben will/kann.

[Assarbad]

Zitat:

Zitat von Luckie (Beitrag 1060496)

@Oliver: Der Code ist schon mehrere Jahre alt. ;)

Pah, dann hast du vergessen für dein zukünftiges Ich ein paar Kommentare zu hinterlassen. Das wird dir hoffentlich eine Lehre sein! :stupid:

Ich sag ja immer, kommentiert nicht was der Code macht - das seh ich nämlich selber - sondern wieso er es macht und wie die Entscheidung es so und nicht anders zu machen zustandekam. :zwinker:

[Luckie]

Meine Güte, das sind noch Jugendsünden. ;)