Bruteforce Algorithmus

wob

@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 $3^{10} = 59049$ Zeichen lang und jede Länge kommt nur 1x vor.

DocShoe

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
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

Swordfish

@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.

Swordfish

@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?

Th69

@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.

Swordfish

@Th69 Das verstehe ich leider nicht. Für soetwas bin ich nicht intelligent genug.

DocShoe

@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;
}

DocShoe

@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;
}