Bruteforce Algorithmus

[Ein ehemaliger Benutzer]

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

[wob]

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

[Swordfish]

@wob sagte in Bruteforce Algorithmus:

und so weiter, dein String wird immer länger!

Dafür hat er den length-Parameter in seinem OP.

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

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

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

[Ein ehemaliger Benutzer]

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

[Ein ehemaliger Benutzer]

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

[Ein ehemaliger Benutzer]

@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

[Ein ehemaliger Benutzer]

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