Code Crack Algorhitmus-> alle möglichen Buchstaben Kombis

Wenn du dir nicht sicher bist, in welchem der anderen Foren du die Frage stellen sollst, dann bist du hier im Forum für allgemeine Fragen sicher richtig.
acidk
User
Beiträge: 75
Registriert: Samstag 6. Januar 2007, 18:54
Wohnort: Braunschweig

Hallo Leute!
Probiere gerade einen "Code-Crack" Algorhitmus, der alle möglichen Buch-
stabenkombinationen durchprobiert. Mein erster Ansatz:

Code: Alles auswählen

alpha1 ='ABCDEFGHIJKLMNOPQRSTUVWXYZ'

for a in alpha1:
    for b in alpha1:      
        print a+b
        for c in alpha1:
                print a+b+c
Meine Fragen:
1)Gibt es eine Möglichkeit, dass ich zuerst alle Zweier und dann alle Dreierkombinationen bekomme?

2)Wie kann ich den Code so vereinfachen, dass ich z.B. angebe "4 Buchstabenkombis", ohne dass ich jedes mal eine separate for-Schleife mit einbinden muss (über eine Range Anweisung vielleicht?)

Vielen Dank!
Benutzeravatar
keppla
User
Beiträge: 483
Registriert: Montag 31. Oktober 2005, 00:12

Falls das nicht ein eher Theoretischer Ansatz ist: Viel Erfolg wirst du mit "Brute Force" typischerweise nicht haben.
1)Gibt es eine Möglichkeit, dass ich zuerst alle Zweier und dann alle Dreierkombinationen bekomme?
Indem du 2) Erledigst, und dann nach Zweier- und Dreierkombis fragst.
2)Wie kann ich den Code so vereinfachen,
Stelle dir eine Funktion vor, die eine beliebige Folge mit einer anderen "Multipliziert",
also

f( ['1', '2'], ['a', 'b'] )
sollte
['1a', '1b', '2a', '2b']
ergeben.

Wenn du diese Funktion hast, musst du sie einfach nur wiederholt auf eine Liste anwenden.

Ich hoffe, das hilft.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Das Stichwort heißt übrigens Permutationen.
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
CM
User
Beiträge: 2464
Registriert: Sonntag 29. August 2004, 19:47
Kontaktdaten:

... und das Cookbook liefert etliche Beispiele.

Gruß,
Christian
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Ein besseres Stichwort als Permutationen wäre wahrscheinlich Variationen mit Zurücklegen.
MfG
HWK

Edit: Eine Implementierung wäre z.B.:

Code: Alles auswählen

>>> def variation(n, code_set, curr_list=['']):
	if n == 0:
		return curr_list
	temp = variation(n - 1, code_set, curr_list)
	result = []
	for c in code_set:
		for term in temp:
			result.append(c + term)
	return result

>>> variation(1, 'ABC')
['A', 'B', 'C']
>>> variation(1, 'ABCDEF')
['A', 'B', 'C', 'D', 'E', 'F']
>>> a = variation(2, 'ABC')
>>> b = variation(1, 'ABC', a)
Y0Gi
User
Beiträge: 1454
Registriert: Freitag 22. September 2006, 23:05
Wohnort: ja

Dieses Snippet habe ich in meinem Archiv gefunden: Generate all possible word permutations
Vielleicht hilft das auch weiter.
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

acidk hat geschrieben:2)Wie kann ich den Code so vereinfachen, dass ich z.B. angebe "4 Buchstabenkombis", ohne dass ich jedes mal eine separate for-Schleife mit einbinden muss (über eine Range Anweisung vielleicht?)
Eine Möglichkeit

Code: Alles auswählen

import string
buchstaben = string.ascii_letters
def wortgenerator(laenge):
    if laenge<1:
        yield ""
        return
    for prefix in wortgenerator(laenge-1):
        for ch in buchstaben:
            yield prefix + ch

# Aufruf, 1. Möglichkeit
sequenz = wortgenerator(4)
print sequenz.next() # aaaa
print sequenz.next() # aaab

# Aufruf, 2. Möglichkeit
for wort in wortgenerator(4):
    print wort
(Edit: fehlendes "return" hinzugefügt)
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Ich hab meine Variante noch mal etwas Ressourcen-schonender geschrieben:

Code: Alles auswählen

>>> def variation(n, code_set, curr_list=['']):
	if n == 0:
		for c in curr_list:
			yield c
	else:
		for term in variation(n - 1, code_set, curr_list):
			for c in code_set:
				yield c + term

>>> a = variation(2, 'ABC')
>>> b = variation(1, 'ABC', a)
>>> for i in b: print i
Im Prinzip entspricht dies aber Joghurts Variante, der mir damit zuvorkam. Der Vorteil bei meiner Variante ist aber, dass man erst Variationen der Länge n überprüfen kann, und dann dieses Zwischenergebnis zur eventuell notwendigen Überprüfung der Variationen mit Länge n+1 verwenden kann. (Hier im Beispiel mit Länge 2 und 3 demonstriert.)
MfG
HWK

Edit: Ist natürlich Blödsinn! :oops:
Wenn man die Zwischenergebnisse ohne Neuberechnung weiterverwenden will, muss man sie auch zwischenspeichern, z.B. als Liste. Ansonsten werden sie immer wieder aufs Neue durch die Generatoren berechnet. Insofern könnte man dann auch gleich meine alte Version, die mit Listen arbeitet, verwenden. Man muss somit selbst entscheiden, was man verwenden will. Wenn man die Länge des Codes Schritt für Schritt erhöht, sind wohl die Listen sinnvoller; wenn man die Länge des Codes kennt, sparen die Generatoren viel Ressourcen.
Benutzeravatar
jens
Python-Forum Veteran
Beiträge: 8502
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:


GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
absolutanon
User
Beiträge: 17
Registriert: Freitag 27. April 2007, 19:43

Hi!

Hab mir zwar nicht alles durchgelesen, aber hab das auch schon mal gebraucht: bei mir siehts so aus:

Code: Alles auswählen

zeichen = "maus123$&etc."
v1 = 0
v2 = 0
v3 = 0
v4 = 0
v5 = 0
v6 = 0
erg = ""
while v6 != len(zeichen):   
    while v5 != len(zeichen):
        while v4 != len(zeichen):
            while v3 != len(zeichen):
                while v2 != len(zeichen):
                    while v1 != len(zeichen):
                        if v6 != 0:
                            print zeichen[v6] + zeichen[v5] + zeichen[v4] + zeichen[v3] + zeichen[v2] + zeichen[v1]
                        else:
                            if v5 != 0:
                                print zeichen[v5] + zeichen[v4] + zeichen[v3] + zeichen[v2] + zeichen[v1]
                            else:
                                if v4 != 0:
                                    print zeichen[v4] + zeichen[v3] + zeichen[v2] + zeichen[v1]
                                else:
                                    if v3 != 0:
                                        print zeichen[v3] + zeichen[v2] + zeichen[v1]
                                    else:
                                        if v2 != 0:
                                            print zeichen[v2] + zeichen[v1]
                                        else:
                                            print zeichen[v1]
                        v1 = v1 + 1
                    v1 = 0
                    v2 = v2 + 1
                v2 = 0
                v3 = v3 + 1
            v3 = 0    
            v4 = v4 + 1
        v4 = 0
        v5 = v5 + 1
    v5 = 0
    v6 = v6 + 1
raw_input("Beenden?")
Benutzeravatar
penguin-p
User
Beiträge: 22
Registriert: Sonntag 19. August 2007, 13:47

Das schreit ja geradezu nach Rekursion ;)
Auch wenn deine Lösung *im prinzip* schneller ist, ist es weder gut zu lesen, noch gut zu schreiben.
Benutzeravatar
HWK
User
Beiträge: 1295
Registriert: Mittwoch 7. Juni 2006, 20:44

Das entspricht ja im Prinzip dem Anfangs-Code von acidk, nur wesentlich umständlicher. Es löst also sicher sein Problem nicht.
MfG
HWK
BlackJack

Eine Möglichkeit für eine nichtrekursive Lösung wäre ein "Zähler" zur Basis der Länge des Alphabets aus dem die Wörter gebildet werden. Dann kann man auch zu einem beliebigen Zählerstand, d.h. einen beliebigem Wort starten. Zum Beispiel um einen abgebrochenen "Brute-Force"-Angriff fortzusetzen.

Irgendwie hatte ich heute meinen masochistischen Tag und habe das mal in (Free)Pascal umgesetzt:

http://paste.pocoo.org/show/3369/

:-)
Benutzeravatar
birkenfeld
Python-Forum Veteran
Beiträge: 1603
Registriert: Montag 20. März 2006, 15:29
Wohnort: Die aufstrebende Universitätsstadt bei München

Oh-oh. Hast du gerade eine Obsolete Language Revival Week gestartet.

Wann kommt Visual Basic?
Dann lieber noch Vim 7 als Windows 7.

http://pythonic.pocoo.org/
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

birkenfeld hat geschrieben:Oh-oh. Hast du gerade eine Obsolete Language Revival Week gestartet.
Und wir haben kein Highlighting für Pascal. Mal sehen, ob ich irgendwann die Woche Zeit finde und da einen Lexer zusammenschreibe. Da müsste man sich natürlich an die Pascal-Syntax erinnern. Aber dazu hab ich ja mehrere Bücher :)
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
BlackJack

Also Pygments hat eigentlich einen Lexer dafür. Hat mich auch gewundert das Pascal oder Delphi nicht in der Dropdown-Box stehen.
Leonidas
Python-Forum Veteran
Beiträge: 16025
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

BlackJack hat geschrieben:Also Pygments hat eigentlich einen Lexer dafür. Hat mich auch gewundert das Pascal oder Delphi nicht in der Dropdown-Box stehen.
Hat sich blackbird wohl gedacht, dass die sowieso keiner nutzen wird. :shock:
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
Joghurt
User
Beiträge: 877
Registriert: Dienstag 15. Februar 2005, 15:07

Leonidas hat geschrieben:
birkenfeld hat geschrieben:Oh-oh. Hast du gerade eine Obsolete Language Revival Week gestartet.
Und wir haben kein Highlighting für Pascal. Mal sehen, ob ich irgendwann die Woche Zeit finde und da einen Lexer zusammenschreibe.
Vergiss nicht COBOL und APL :wink:
Benutzeravatar
penguin-p
User
Beiträge: 22
Registriert: Sonntag 19. August 2007, 13:47

Und Brainfuck :D
BlackJack

Dafür gibt es schon lange einen Lexer in Pygments. :-)
Antworten