Brute-force-Algorithmus für Permutationen

F

Freak2k

Erfahrenes Mitglied
Hallo,

ich habe einen String = "aaa"
und ein Array erlaubter zeichen = {'a','b','c'}
jetzt brauche ich eine funktion, die saemtliche woerter durch-iteriert....
aab -> aac -> aba ....
ich muss irgendwo ne denkblockade haben...
 
Um diese Leiche hier mal mit einer simplen Lösung zu beantworten.. ich zerbrech mir jedesmal selbst immer wieder das Hirn und werd mit google nicht richtig fündig..

Alphabet anlegen:

Code: 
    char[] alphabet =  {'a','b','c','d','e',
                        'f','g','h','i','j',
                        'k','l','m','n','o',
                        'p','q','r','s','t',
                        'u','v','w','x','y',
                        'z'};

..dazu 3 Methoden:

Code: 
    public String nextWord(String word) {
        return nextWord(word, word.length()-1);
    }

    public String nextWord(String word, int stelle) {
        char[] wordArray = word.toCharArray();
        if (wordArray.length == 0){
            return String.valueOf(alphabet[0]);
        }else if(wordArray[stelle] == alphabet[alphabet.length - 1]) {
            wordArray[stelle] = alphabet[0];
            if (stelle > 0) {
                return nextWord(String.valueOf(wordArray), stelle - 1);
            }
            else{
                return alphabet[0]+String.valueOf(wordArray);
            }
        }
         else{
            for (int i = 0; i< alphabet.length; i++){
                if (wordArray[stelle] == alphabet[i]){
                    wordArray[stelle] = alphabet[i+1];
                    break;
                }
            }
            return String.valueOf(wordArray);
        }
    }

    public void generateWords(String start, long count) {
        String word = start;
        long wordcount = 0;
        while (wordcount < count){
            wordcount++;
            word = nextWord(word);
            System.out.println(wordcount + ": " + word);
        }
    }

und mit folgendem Beispielaufruf (startwort, Anzahl gewünschter Wörter) starten:

Code: 
generateWords("", 18278);

Das Beispiel erzeugt alle Wörter von a bis zzz
Das sind 18278 Wörter.

Für eine Stelle sind 26 Wörter möglich.
Für zwei Stellen sind 26*26 + 26 = 702 Wörter möglich.
Für drei Stellen sind 26*26*26 + 702 Wörter möglich.
..usw

Die Wörter von a bis z erhält man durch den Aufruf:

Code: 
generateWords("", 26);
Code: 
1: a
2: b
3: c
4: d
5: e
6: f
7: g
8: h
9: i
10: j
11: k
12: l
13: m
14: n
15: o
16: p
17: q
18: r
19: s
20: t
21: u
22: v
23: w
24: x
25: y
26: z

entsprechend erhält man bei folgendem Aufruf die Wörter von b bis aa:

Code: 
generateWords("a", 26);
Code: 
1: b
2: c
3: d
4: e
5: f
6: g
7: h
8: i
9: j
10: k
11: l
12: m
13: n
14: o
15: p
16: q
17: r
18: s
19: t
20: u
21: v
22: w
23: x
24: y
25: z
26: aa

beliebige Alphabete sollten möglich sein, doppelte Elemente gilt es zu vermeiden ;)

Ich denke, die Kommentare sollte sich jemand der den Code verwenden möchte selbst erarbeiten können ;)
Der Algorithmus funktioniert sozusagen wie natürliches Zählen. Also zum Beispiel:
..
8 + 1 = 9
9 + 1 = 10
10 + 1 = 11
..
 
Zuletzt bearbeitet:
Maddimini hat gesagt.:
Hallo,

unter Punkt 2d findest du eine Bruteforce Attacke mit einem gut strukturiertem Quellcode ;)

http://www.schule.bayern.de/bluejprojekte/

Dafür brauchst du eventuell BlueJ ;) das ist aber kostenlos runterladbar ;)
Zum Vergrößern anklicken....

Bist du Lehrer oder Schüler? ;)

naja.. ausser mir war seit 3 Jahren niemand mehr in dem Thread aktiv, und ich habe selbst eine Lösung entwickelt und gepostet.

1) Soweit ich deinen Code auf die Schnelle gesehn habe braucht der nirgends BlueJ.

2) Die von dir genannte Methode hatte ich schon versucht, allerdings für meine Zwecke als nicht brauchbar eingestuft, da die Reihenfolge der Wörter "unnatürlich" und damit das Aufteilen in mehrere Chunks keine triviale Aufgabe mehr ist.
.. auf a folgt aa, darauf aaa ...später dann irgendwann b, bb, ... usw.
Besser ist die Reihenfolge a, b, .. z, aa, ab, ac, .. ba, bb, ..

3) sooo gut strukturiert find ich den von dir genannten Code auch nicht wirklich ;) unbenutzte Parameter, unpassende schleife gewählt ..etc.. :P

Code: 
    private void NextString(String s) 
    {

        int i = 0;

        
        while (i< zeichenvorrat.length && !gefunden && !abgebrochen) 
        {
            String sneu;
            sneu=s + new Character(zeichenvorrat[i]).toString();
            if(sneu.equals(passwort))
            {
                gefunden=true;
                f.ErgebnisSetzen(sneu, System.nanoTime()-startNanoTime);
            }
            if (sneu.length() <= maxlen-1) 
            {
                NextString(sneu);
            }
            i++;
        }
    }

meine Variante für diese Methode sah so aus:
Code: 
    public void generateRecursive(String start, int length) {
        System.out.println(start);
        if (start.length() < length) {
            for (int i = 0; i < alphabet.length; i++) {
                generateRecursive(start + alphabet[i], length);
            }
        }
    }
"schön" kurz und funktioniert..
..allerdings halte ich am Ende die erste von mir beschriebene Methode trotzdem für besser. ;)
Performanceunterschiede sind nur minimal, dafür kann ich dann aber einfach vorrausberechnen welches zBsp das 10.000.000.000 Passwort sein wird und einen weiteren Chunk an dieser Stelle beginnen lassen..
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück