alle kombinationen von zeichen in einem string
In Python 5000 werden wir dann endlich haben:
yipyip
Code: Alles auswählen
from all_problems import my_problem
my_problem.solve()
yipyip
Ach was, hab ich jetzt schon:yipyip hat geschrieben:In Python 5000 werden wir dann endlich haben[...]
Code: Alles auswählen
In [11]: import sys
In [12]: from types import ModuleType
In [13]: sys.modules['all_problems'] = ModuleType('all_problems')
In [14]: class my_problem(object):
....: @staticmethod
....: def solve():
....: return 42
....:
In [15]: sys.modules['all_problems'].my_problem = my_problem
In [16]: from all_problems import my_problem
In [17]: my_problem.solve()
Out[17]: 42
Dann wird's aber langweiligyipyip hat geschrieben:In Python 5000 werden wir dann endlich haben:Code: Alles auswählen
from all_problems import my_problem my_problem.solve()
yipyip
Wenn du daran interessiert bist schau dir mal Zine an, dort wird das Produktiv genutzt um ein Datenbank Modul zu erzeugen, ziemlich coole Sache.yipyip hat geschrieben:@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann.
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
MERCI!
der C-code, den abgdf gepostet hat, funktioniert wunderbar schnell. leider kenne ich mich mit C so gut wie gar nicht aus. koennte mir vielleicht jemand sagen, wie man den code so erweitern koennte, dass er auch teilstrings erzeugt, und nicht nur alle kombinationen (das sind ja jetzt wirklich kombinationen )?
außerdem habe ich mir mal python 2.6 zusaetzlich installiert, und das hier ausprobiert:
klappt auch wunderbar, ist nur - was ja auch logisch ist - deutlich langsamer als die methode in C, die ich eben bevorzugen wuerde.
lg
roschi
der C-code, den abgdf gepostet hat, funktioniert wunderbar schnell. leider kenne ich mich mit C so gut wie gar nicht aus. koennte mir vielleicht jemand sagen, wie man den code so erweitern koennte, dass er auch teilstrings erzeugt, und nicht nur alle kombinationen (das sind ja jetzt wirklich kombinationen )?
außerdem habe ich mir mal python 2.6 zusaetzlich installiert, und das hier ausprobiert:
Code: Alles auswählen
def perm(s):
for i in xrange(len(s) + 1):
for combination in combinations(s, i):
for permutation in permutations(combination):
if permutation:
print "".join(permutation)
perm("eis")
lg
roschi
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
Wie wärs denn wenn du diesen unsinnigen ansatz mit liste generieren komplett verwirfst?
Soll bestimmt ein Passwortcracker per Bruteforce werden oder?
Auf einem normalen Rechner wirst du wohl mit einem generator arbeiten müssen, dann brauchst du auch nicht soviel RAM.
Alles andere halte ich für ausserhalb deiner hardwaremöglichkeiten ...
Soll bestimmt ein Passwortcracker per Bruteforce werden oder?
Auf einem normalen Rechner wirst du wohl mit einem generator arbeiten müssen, dann brauchst du auch nicht soviel RAM.
Alles andere halte ich für ausserhalb deiner hardwaremöglichkeiten ...
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
hallo!
@Mad Marty:
die liste habe ich jetzt rausgenommen. ist ja klar, das es damit bei so großen nicht klappen kann. ich gebe jetzt alles nach stdout aus und leite es in eine datei um.
nein, es soll kein bruteforce passwort cracker werden. ich moechte am ende jedes ergebnis auf presens in einem woerterbuch pruefen, um alle sinnvollen woerter aus dem ursprungs-string zu erhalten.
lg
roschi
PS: ich habe von etwa um 11:00 uhr bis jetzt 81 GB an daten mit der python-methode erzeugt.
@Mad Marty:
die liste habe ich jetzt rausgenommen. ist ja klar, das es damit bei so großen nicht klappen kann. ich gebe jetzt alles nach stdout aus und leite es in eine datei um.
nein, es soll kein bruteforce passwort cracker werden. ich moechte am ende jedes ergebnis auf presens in einem woerterbuch pruefen, um alle sinnvollen woerter aus dem ursprungs-string zu erhalten.
lg
roschi
PS: ich habe von etwa um 11:00 uhr bis jetzt 81 GB an daten mit der python-methode erzeugt.
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
Wie wäre es mit Kölner Phonetik oder Soundex?
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
ich glaube, wir reden aneinander vorbei. ich will keine aenlich klingenden woerter haben, sondern welche, die man aus einigen oder allen buchstaben des ursprungswortes bilden kann - egal in welcher reihenfolge die buchstaben verwendet werden.DasIch hat geschrieben:Wie wäre es mit Kölner Phonetik oder Soundex?
lg
roschi
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
@roschi: Argh! Bist Du wahnsinnig!? Ums mal vorsichtig auszudrücken.
Da geht man besser den umgekehrten Weg und testet jedes Wort im Wörterbuch ob man es mit den vorhandenen Buchstaben bilden kann. Das durfte *deutlich* schneller sein als 81 GiB an Daten zu erzeugen von denen man im Vorfeld schon weiss, dass 99% davon nicht im Wörterbuch vorkommen werden.
Simpelste Methode zum finden von Anagrammen ist das sortieren der Buchstaben im Suchwort und allen Worten die untersucht werden. Wenn die dann gleich sind, hat man einen Treffer.
PS: Beispiel:
Auf die Art kannst Du auch das komplette Wörterbuch mal vorverarbeiten und schauen welche Anagramme da enthalten sind.
Da geht man besser den umgekehrten Weg und testet jedes Wort im Wörterbuch ob man es mit den vorhandenen Buchstaben bilden kann. Das durfte *deutlich* schneller sein als 81 GiB an Daten zu erzeugen von denen man im Vorfeld schon weiss, dass 99% davon nicht im Wörterbuch vorkommen werden.
Simpelste Methode zum finden von Anagrammen ist das sortieren der Buchstaben im Suchwort und allen Worten die untersucht werden. Wenn die dann gleich sind, hat man einen Treffer.
PS: Beispiel:
Code: Alles auswählen
In [301]: sorted('schaeuble')
Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
In [302]: sorted('belausche')
Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
@BlackJack:
es gibt eben doch noch leute, die mehr nachdenken als ich.
ich haette wohl gleich sagen sollen, was ich vorhabe.
vielen, vielen, lieben dank an alle, die versucht haben, mir zu helfen!
lg
roschi
es gibt eben doch noch leute, die mehr nachdenken als ich.
ich haette wohl gleich sagen sollen, was ich vorhabe.
vielen, vielen, lieben dank an alle, die versucht haben, mir zu helfen!
lg
roschi
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
-
- Python-Forum Veteran
- Beiträge: 16025
- Registriert: Freitag 20. Juni 2003, 16:30
- Kontaktdaten:
Ich sehe, auch hier gibt es Leser von Fefes BlogBlackJack hat geschrieben:Code: Alles auswählen
In [301]: sorted('schaeuble') Out[301]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u'] In [302]: sorted('belausche') Out[302]: ['a', 'b', 'c', 'e', 'e', 'h', 'l', 's', 'u']
My god, it's full of CARs! | Leonidasvoice vs (former) Modvoice
'belausche' ist ein Anagramm von 'schaeuble' ? Wie geil ist das denn ?
Es könnte sein, daß es schon genügt, nur die Anzahl der einzelnen Buchstaben zu vergleichen. "string.count()" ist da sehr hilfreich.
Gruß
Es könnte sein, daß es schon genügt, nur die Anzahl der einzelnen Buchstaben zu vergleichen. "string.count()" ist da sehr hilfreich.
Gruß
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
so, falls es nun jemanden interessieren sollte:
das funktioniert einwandfrei und natuerlich bedeutend schneller ich hab ein 3,4 MB großes woerterbuch, werde mir aber bald ein deutlich groeßeres besorgen. naja, jedenfalls muss ich keine 81 GB daten erzeugen
ein riesengroßes dankeschoen nochmal !
lg
roschi
Code: Alles auswählen
# -*- coding: iso-8859-15 -*-
import sys
def main(inputstring, dictfile="dict.txt"):
fi = file(dictfile, "r")
entries = fi.read().split()
fi.close()
inputstring = inputstring.lower()
raw_chars = {}
for char in inputstring:
raw_chars[char] = inputstring.count(char)
data = []
for entrie in entries:
entrie_show = entrie
entrie = entrie.lower()
chars_copy = {}
for item in raw_chars:
chars_copy[item] = raw_chars[item]
is_okay = True
for char in entrie:
if char in chars_copy and chars_copy[char] > 0:
chars_copy[char] -= 1
else:
is_okay = False
if is_okay:
data.append(entrie_show)
fo = file("out.txt", "w")
fo.write("\n".join(data + [""]))
fo.close()
main(sys.argv[1])
ein riesengroßes dankeschoen nochmal !
lg
roschi
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]
Ist von der Laufzeit natürlich besser, aber immer noch fürchterlich kompliziert und verbrät immer noch eine Menge unnötiger Rechenzeit.
Die Berechnung von `raw_chars` hat quadratische Laufzeit, weil `count()` für jedes Zeichen jedes mal wieder `inputstring` von vorne bis hinten durchläuft.
Ein Dictionary kann man einfacher kopieren, in dem man das alte `dict()` als Argument gibt, also Zeile 20-22 wird zu ``chars_copy = dict(raw_chars)``.
Wenn `is_okay` auf `False` gesetzt wird, macht es keinen Sinn die Schleife noch weiter abzuarbeien. Wenn man den Test in eine Funktion auslagert, kann man sich `is_okay` komplett sparen und an der Stelle gleich ein ``return False`` schreiben.
Wobei ich mir nicht sicher bin, ob das Programm wirklich das macht, was es soll, weil auch Einträge in `data` kommen, die nicht alle Buchstaben des Eingabewortes verwenden. Ist das gewollt?
Man könnte ganz am Anfang auch noch eine Bedingung setzen, die die Längen überprüft. Wenn das Wort aus dem Wörterbuch länger als die Eingabe ist, kann man sich den restlichen Test sparen.
Ansonsten würde ich den Code so schreiben, dass das Wörterbuch nicht komplett auf einmal in den Speicher gelesen wird. Auch wenn ein paar Megabyte für heutige Rechner kein Problem mehr darstellen.
Die Funktion würde bei mir die Eingabe und ein "iterable" erhalten und selbst einen Iterator/Generator zurück geben. So ist sie am flexiblesten von der konkreten Ein- und Ausgabe getrennt.
PS: Kleines Beispiel wie ich einen Anagramm-Finder schreiben würde:
Die Berechnung von `raw_chars` hat quadratische Laufzeit, weil `count()` für jedes Zeichen jedes mal wieder `inputstring` von vorne bis hinten durchläuft.
Ein Dictionary kann man einfacher kopieren, in dem man das alte `dict()` als Argument gibt, also Zeile 20-22 wird zu ``chars_copy = dict(raw_chars)``.
Wenn `is_okay` auf `False` gesetzt wird, macht es keinen Sinn die Schleife noch weiter abzuarbeien. Wenn man den Test in eine Funktion auslagert, kann man sich `is_okay` komplett sparen und an der Stelle gleich ein ``return False`` schreiben.
Wobei ich mir nicht sicher bin, ob das Programm wirklich das macht, was es soll, weil auch Einträge in `data` kommen, die nicht alle Buchstaben des Eingabewortes verwenden. Ist das gewollt?
Man könnte ganz am Anfang auch noch eine Bedingung setzen, die die Längen überprüft. Wenn das Wort aus dem Wörterbuch länger als die Eingabe ist, kann man sich den restlichen Test sparen.
Ansonsten würde ich den Code so schreiben, dass das Wörterbuch nicht komplett auf einmal in den Speicher gelesen wird. Auch wenn ein paar Megabyte für heutige Rechner kein Problem mehr darstellen.
Die Funktion würde bei mir die Eingabe und ein "iterable" erhalten und selbst einen Iterator/Generator zurück geben. So ist sie am flexiblesten von der konkreten Ein- und Ausgabe getrennt.
PS: Kleines Beispiel wie ich einen Anagramm-Finder schreiben würde:
Code: Alles auswählen
import codecs
import sys
def normalize(word):
return sorted(word.lower())
def iter_anagrams(word, words, normalize=normalize):
key = normalize(word)
return (w for w in words if len(key) == len(w) and normalize(w) == key)
def main():
word_file = codecs.open('/usr/share/dict/ngerman', 'r', 'iso-8859-1')
word = sys.argv[1].decode('utf-8')
anagrams = iter_anagrams(word, (w.strip() for w in word_file))
sys.stdout.writelines(a.encode('utf-8') + '\n' for a in anagrams)
word_file.close()
- roschi
- User
- Beiträge: 225
- Registriert: Samstag 29. März 2008, 18:58
- Wohnort: Thueringen, Deutschland
- Kontaktdaten:
hallo!
@BlackJack:
ja, es ist gewollt, das auch woerter gefunden werden, die nicht alle zeichen des inputstrings verwenden. vielen dank fuer die verbesserungsvorschlaege! es ist wirklich schneller - vor allem durch das pruefen der laenge am anfang. ich moechte ja nicht unbedingt anagramme finden, sondern, wie schon gesagt, auch woerter, die nicht alles aus dem inputstring nutzen.
ein riesengroßes dankeschoen und einen schoenen abend noch!
lg
roschi
@BlackJack:
ja, es ist gewollt, das auch woerter gefunden werden, die nicht alle zeichen des inputstrings verwenden. vielen dank fuer die verbesserungsvorschlaege! es ist wirklich schneller - vor allem durch das pruefen der laenge am anfang. ich moechte ja nicht unbedingt anagramme finden, sondern, wie schon gesagt, auch woerter, die nicht alles aus dem inputstring nutzen.
ein riesengroßes dankeschoen und einen schoenen abend noch!
lg
roschi
[size=117]Fuer Alle, die in Python einsteigen wollen, kann ich das Buch [url=http://abop-german.berlios.de/]A Byte of Python[/url] nur waermstens empfehlen![/size]