Bruteforce Algorithmus
-
Hallo,
Wie mache ich am besten einen aufsteigenden Bruteforce Algorithmus?
Ich habe selbst was zusammen geschustert
bool bruteforce(std::size_t max_length, const std::string& range, std::function<bool(const std::string& )> callback){ std::size_t max_combinations = std::pow(range.size(), max_length); std::string current; for(std::size_t n{}; n < max_combinations; ++n){ current += range[n % range.size()]; if(callback(current)) return true; } return false; }
Aber komme damit echt nicht weiter. Weiß jemand was ich da sonst noch tun muss?
Danke jedenfalls.
Liebe Grüße
-
@eigenartig sagte in Bruteforce Algorithmus:
Aber komme damit echt nicht weiter. Weiß jemand was ich da sonst noch tun muss?
Schritt 1: in Worten erklären, was du eigentlich erreichen willst und dazu ggf. ein paar kleine Beispiel bringen.
Denn was meinst du mit "aufsteigender Bruteforce-Algorithmus"? Was soll das sein? Du scheinst irgendwas mit einem String machen zu wollen, der immer länger wird.
-
Ja also ich habe eine gegebene Reihe [ABC], welche ich aufsteigend auf jedes mögliche Wort testen will.
Also sowas in der Art:
A B C AA AB AC BA BB BC CA CB CC AAA AAB AAC ABA ABB ABC ACA ACB ACC BAA BAB BAC BBA BBB BBC BCA BCB BCC CAA CAB CAC CBA CBB CBC CCA CCB CCC
-
Dein Algorithmus macht aber:
A
AB
ABC
ABCA
ABCAB
...
und so weiter, dein String wird immer länger!Für eine feste Länge kannst du dir mal https://en.cppreference.com/w/cpp/algorithm/next_permutation anschauen. Edit: passt nicht, da du ja auch AAA usw. haben willst (also mehr As, als in Range vorhanden).
-
@wob sagte in Bruteforce Algorithmus:
und so weiter, dein String wird immer länger!
Dafür hat er den
length
-Parameter in seinem OP.
-
@Swordfish sagte in Bruteforce Algorithmus:
Dafür hat er den length-Parameter in seinem OP.
Vielleicht gedacht. Aber der begrenzt anders als man denkt. Setzt man im obigen Code
max_length=10
undrange="ABC"
ein, dann wird der String im obigen Schema bis zu Zeichen lang und jede Länge kommt nur 1x vor.
-
Also....
- du initialisierst jedes Zeichen des testcase der Länge N mit dem ersten Zeichen des Alphabets (deiner range)
- Callback Aufruf mit dem testcase
- du guckst nach, ob das 1. Zeichen des Testcase das letzte Zeichen des Alphabets ist.
- ja -> ersetze es durch das erste Zeichen des Alphabets (Überlauf behandeln)
Ist das ersetzte Zeichen das letzte des Testcase?- ja -> fertig
- nein -> wiederhole den Vorgang für das nächsten Zeichen des testcase
- nein -> ersetze es durch den nächsten Zeichen des Alphabets
- ja -> ersetze es durch das erste Zeichen des Alphabets (Überlauf behandeln)
- goto 2
[ABC] ,3 ->
AAA -> BAA -> CAA -> ABA -> BBA -> CBA -> ACA -> BCA -> CCA ->
AAB -> BAB -> CAB -> ABB -> BBB -> CBB -> ACB -> BCB -> CCB ->
AAC -> BAC -> CAC -> ABC -> BBC -> CBC -> ACC -> BCC -> CCC -> fertig
-
@wob sagte in Bruteforce Algorithmus:
Vielleicht gedacht.
Ja, deswegen beschäftige ich mich damit auch nicht. Es fehlt eine klare Definition der Schnittstelle.
@DocShoe Ja, eben nicht. Er will mit
"A"
,"B"
,"C"
,"AA"
,"AB"
, ... anfangen.
-
@Swordfish ja so will ich anfangen.
-
@eigenartig Das ist ja schön. Was ist wenn
max_length
länger ist alsrange
? Was soll das/der callback?
-
@Swordfish sagte in Bruteforce Algorithmus:
@eigenartig Das ist ja schön. Was ist wenn
max_length
länger ist alsrange
? Was soll das/der callback?Ok dann ohne
max_length
. Einfach nur von 1 bis 3?
-
@Swordfish: Der Algo von @DocShoe ist schon richtig, nur daß dann noch zusätzlich über den 2. Parameter iteriert werden muß, d.h.
[ABC], x
mitx = 1...length
.
-
@Th69 Das verstehe ich leider nicht. Für soetwas bin ich nicht intelligent genug.
-
@Swordfish sagte in Bruteforce Algorithmus:
@wob sagte in Bruteforce Algorithmus:
Vielleicht gedacht.
Ja, deswegen beschäftige ich mich damit auch nicht. Es fehlt eine klare Definition der Schnittstelle.
@DocShoe Ja, eben nicht. Er will mit
"A"
,"B"
,"C"
,"AA"
,"AB"
, ... anfangen.Ich traue jedem zu, drumrum eine for-Schleife zu setzen...
Im Grunde ist es doch nix anderes wie ein +1 Addition im Dezimalsystem. Du erhöhst die niederwertigste Stelle und behandelst solange Überläufe, bis keine Überläufe mehr auftreten. Oder du den Definitionsbereich verlässt.
-
@Swordfish ich versuche das Beispiel von @DocShoe zu implementieren, aber klappt noch nicht so ganz.
bool bruteforce(std::size_t max_length, const std::string& range, std::function<bool(const std::string& )> callback){ std::string current(max_length, range.front()); for(std::size_t m{}; m < max_length; ++m){ for(std::size_t n{}; n < range.size(); ++n){ std::size_t idx{}; while(idx < current.size() && current[idx] == range.back()){ current[idx] = range.front(); ++idx; } current[m] = range[n]; if(callback(current)) return true; } } return false; }
-
@eigenartig
Schreib´ für die Bestimmung der nächsten Permutation eine Funktion, das macht die Sache wesentlich einfacher.
Und was sollen wir mit der Fehlermeldung "klappt noch nicht so ganz anfangen?". Beschreib das erwartete Verhalten und das, was dein Programm tut, dann kann man dir auch helfen.Lösung auf ideone
-
Ok, sieht einfacher aus als ich dachte. Danke.
EDIT: Ich habs schon irgendwie geschafft das zu implementieren, aber ich bin die
std::deque<>
nicht wirklich los geworden. Ich habe das aus einer rekursiven Funktion entnommen. Sprengt den Stack nicht:bool bruteforce(std::size_t max, const std::string& range, std::function<bool(const std::string& )> callback){ std::deque<std::string> roots; std::string current; do{ if(roots.size()){ current = roots.front(); roots.pop_front(); } if(current.size() == max) continue; for(char c : range){ roots.push_back(current + c); if(callback(roots.back())) return true; } } while(roots.size()); return false; }