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 und range="ABC" ein, dann wird der String im obigen Schema bis zu 310=590493^{10} = 59049 Zeichen lang und jede Länge kommt nur 1x vor.



  • Also....

    1. du initialisierst jedes Zeichen des testcase der Länge N mit dem ersten Zeichen des Alphabets (deiner range)
    2. Callback Aufruf mit dem testcase
    3. 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
    4. 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 als range? Was soll das/der callback?



  • @Swordfish sagte in Bruteforce Algorithmus:

    @eigenartig Das ist ja schön. Was ist wenn max_length länger ist als range? 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 mit x = 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;
    }
    

Anmelden zum Antworten