alle kombinationen von zeichen in einem string

[numerix]

Das ist ja genau das, was ich schon in meinem ersten Posting (allerdings ohne Code) gesagt hatte: In Python 2.6 schnell erledigt. Hat mich die ganze Zeit gewundert, warum so lange daran herumgebastelt wurde ...

[yipyip]

In Python 5000 werden wir dann endlich haben:

Code: Alles auswählen

from all_problems import my_problem
my_problem.solve()

yipyip

[DasIch]

In Python 5000 werden wir dann endlich haben[...]

Ach was, hab ich jetzt schon:

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

[numerix]

In Python 5000 werden wir dann endlich haben:

Code: Alles auswählen

from all_problems import my_problem
my_problem.solve()

yipyip

Dann wird's aber langweilig

[yipyip]

@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann.

@numerix:
Nicht traurig sein, in diesem Forum
wird es auch weiterhin genug zu tun geben.


yipyip

[DasIch]

@DasIch:
Danke, ...hat mich wieder mal verblüfft, was man
in Python alles anstellen kann.

Wenn du daran interessiert bist schau dir mal Zine an, dort wird das Produktiv genutzt um ein Datenbank Modul zu erzeugen, ziemlich coole Sache.

[roschi]

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:

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

klappt auch wunderbar, ist nur - was ja auch logisch ist - deutlich langsamer als die methode in C, die ich eben bevorzugen wuerde.

lg
roschi

[Mad-Marty]

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

[roschi]

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.

[DasIch]

Wie wäre es mit Kölner Phonetik oder Soundex?

[roschi]

Wie wäre es mit Kölner Phonetik oder Soundex?

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.

lg
roschi

[BlackJack]

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

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']

Auf die Art kannst Du auch das komplette Wörterbuch mal vorverarbeiten und schauen welche Anagramme da enthalten sind.

[roschi]

@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

[Leonidas]

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']

Ich sehe, auch hier gibt es Leser von Fefes Blog

[abgdf]

'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ß

[roschi]

so, falls es nun jemanden interessieren sollte:

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

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

[BlackJack]

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:

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]

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