Das deutsche Python-Forum

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!

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.

Das Stichwort heißt übrigens Permutationen.

... und das Cookbook liefert etliche Beispiele.

Gruß,
Christian

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)

Dieses Snippet habe ich in meinem Archiv gefunden: Generate all possible word permutations
Vielleicht hilft das auch weiter.

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)

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!

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.

Nicht zu vergessen: http://www.python-forum.de/topic-1812.html

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?")

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.

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

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/

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

Wann kommt Visual Basic?

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

Also Pygments hat eigentlich einen Lexer dafür. Hat mich auch gewundert das Pascal oder Delphi nicht in der Dropdown-Box stehen.

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.

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

Und Brainfuck

Dafür gibt es schon lange einen Lexer in Pygments.

Das deutsche Python-Forum

Code Crack Algorhitmus-> alle möglichen Buchstaben Kombis

Code Crack Algorhitmus-> alle möglichen Buchstaben Kombis

Re: Code Crack Algorhitmus-> alle möglichen Buchstaben Ko