Seite 1 von 2
Anagramm-Generator
Verfasst: Montag 29. November 2010, 23:42
von derdon
Joa, hatte Langeweile:
http://paste.pocoo.org/show/297798/
Beispielaufruf:
Re: Anagramm-Generator
Verfasst: Dienstag 30. November 2010, 00:03
von EyDu
Bei längeren Wörtern lohnt es sich vielleicht das Wörterbuch als Menge zu halten, aber darüber hast du sicher auch schon nachgedacht.
Sebastian
Re: Anagramm-Generator
Verfasst: Dienstag 30. November 2010, 00:16
von BlackJack
@derdon: Alle Permutationen zu bilden mag bei Drei-Buchstaben-Wörtern ja noch in Ordnung sein, aber das ist echt ineffizient.
Du musst ja eh alle Worte aus der Datei auslesen -- dabei kannst Du auch ein Dictionary erstellen was die sortierten Buchstaben eines Wortes auf Listen mit eben den Worten abbildet. Das ist der übliche Weg über den man so etwas löst. Also die Worte 'dog' und 'god' würden dann als folgendes Schlüssel/Wert-Paar im Dictionary landen: ``('dgo', ['dog', 'got'])``. Wenn das Dictionary dann aufgebaut ist, braucht man nur noch die Buchstaben von der Eingabe vom Benutzer sortieren und kann sofort auf die Liste mit allen Anagrammen dazu zugreifen.
Re: Anagramm-Generator
Verfasst: Dienstag 30. November 2010, 00:31
von BlackJack
@derdon: Kannst folgendes ja mal auf 'certifications' ('rectifications'), 'antiparticles' ('paternalistic'), oder 'imperfections' ('perfectionism') loslassen und die Laufzeiten vergleichen:
Code: Alles auswählen
import sys
from collections import defaultdict
def sort_word(word):
return ''.join(sorted(word))
def main():
sorted2anagrams = defaultdict(list)
with open('/usr/share/dict/words') as lines:
for line in lines:
word = line.strip()
sorted2anagrams[sort_word(word)].append(word)
print sorted2anagrams.get(sort_word(sys.argv[1]), 'NO ANAGRAM FOUND')
if __name__ == '__main__':
main()
Re: Anagramm-Generator
Verfasst: Dienstag 30. November 2010, 10:29
von snafu
Eine Idee für komplexere Anwendungsfälle:
Code: Alles auswählen
import string
_dummy_table = string.maketrans('', '')
_delete_chars = string.punctuation + string.whitespace
def make_anagramable(s):
translated = s.translate(_dummy_table, _delete_chars)
return ''.join(sorted(translated.lower()))
def word_for_anagram(anagram, words):
anagramabled = make_anagramable(anagram)
for word in words:
if anagramabled == make_anagramable(word):
return word
def test(anagram='Fr. Inge C. Sonst, Rheine', source='/usr/share/dict/ngerman'):
with open(source) as words:
print '%s ist von Beruf %s' %(anagram, word_for_anagram(anagram, words))
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 15:43
von Xynon1
Habe mal snafus Programm erweitert, könnte aber etwas Hilfe gebrauchen, um es zu optimieren, da es nicht besonders schnell ist.
Ziel war es, dies auch für Sätze zu bieten, in dem man im Moment noch die Anagram Wortzahl festlegt, doch seht selbst:
Code: Alles auswählen
import string
import itertools
class Anagram(object):
def __init__(self, source="../dict/ogerman"):
self.dummy_table = string.maketrans('', '')
self.delete_chars = string.punctuation + string.whitespace
with open(source) as words:
self.words = words.readlines()
def make_anagramable(self, string):
translated = string.translate(self.dummy_table, self.delete_chars)
return "".join(sorted(translated.lower()))
def word_for_anagram(self, anagram, words):
anagramabled = self.make_anagramable(anagram)
for word in words:
if anagramabled == self.make_anagramable(word):
yield word.strip()
def text_for_anagram(self, anagram, words):
a = list(self.make_anagramable(anagram))
for word in words:
w = list(self.make_anagramable(word))
for char in a:
if char in w:
del w[w.index(char)]
if len(w) == 0:
yield word
def combine_words(self, anagram, words, max_words):
lenght = len(anagram)
anagramabled = self.make_anagramable(anagram)
for word_combination in itertools.combinations(words, max_words):
word = self.make_anagramable("".join(word_combination))
if len(word) <= lenght:
if anagramabled == word:
yield " ".join(word_combination).translate(self.dummy_table, "\n").title()
def test_word(self, anagram="Fr. Inge C. Sonst, Rheine"):
for word in self.word_for_anagram(anagram, self.words):
print("{0}: {1}".format(anagram, word))
def test_text(self, anagram, max_words=3):
if max_words == 1:
self.test_word(anagram)
return
probabilities = list(self.text_for_anagram(anagram, self.words))
print(anagram + ": ")
for word in self.combine_words(anagram, probabilities, max_words):
print(word)
if __name__ == "__main__":
anagram = Anagram()
anagram.test_text("Antigone", 1)
print("")
anagram.test_text("Fr. Inge C. Sonst, Rheine", 2)
print("")
anagram.test_text("Hallo Welt!", 2)
print("")
anagram.test_text("Ich sollte ein Anagram sein.", 3)
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 16:01
von ms4py
Xynon1 hat geschrieben:Habe mal snafus Programm erweitert, könnte aber etwas Hilfe gebrauchen, um es zu optimieren, da es nicht besonders schnell ist.
Ziel war es, dies auch für Sätze zu bieten, in dem man im Moment noch die Anagram Wortzahl festlegt, doch seht selbst:
Die Lösung von BlackJack dürfte doch ziemlich performant sein, hast du die noch nicht getestet?
http://python-forum.de/viewtopic.php?p=186458#p186458
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 16:06
von Xynon1
Doch habe ich, aber snafus war einfacher auszubauen
Ja, werde das nochmal anhand BlackJacks funktion aufziehen und hier posten,
dennoch würde ich gerne ein paar Flaschenhälse in meinem Programm beheben.
Bevor ich die selben Fehler wieder mache.
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 18:25
von Xynon1
So, noch jemand verbesserungsvorschläge ?
Code: Alles auswählen
from collections import defaultdict
import string
import itertools
class Anagram(object):
def __init__(self, anagram="Fr. Inge C. Sonst, Rheine", words=1, source="../dict/ngerman"):
self.dummy_table = string.maketrans("", "")
self.delete_chars = string.punctuation + string.whitespace
self.words = defaultdict(list)
self.max_words = words
self.orginal = anagram
self.anagram = self.sort_word(anagram)
with open(source) as lines:
for line in lines:
word = line.strip()
self.words[self.sort_word(word)].append(word)
def __str__(self):
if self.max_words > 1:
combinations = list(self.text_for_anagram())
return self.orginal + ": " + "\n".join(self.combine_words(combinations))
return("{0}: {1}".format(self.orginal, self.words.get(self.anagram), "No anagram found."))
def sort_word(self, word):
return "".join(sorted(word.translate(self.dummy_table, self.delete_chars).lower()))
def text_for_anagram(self):
for word in self.words:
chars = list(word)
for char in self.anagram:
if char in chars:
del chars[chars.index(char)]
if len(chars) == 0:
yield word
def combine_words(self, combinations):
for word_combination in itertools.combinations(combinations, self.max_words):
if self.anagram == "".join(sorted("".join(word_combination))):
words = itertools.product(*[x for x in (self.words.get(word) for word in word_combination)])
for word in words:
print(word)
yield " ".join(word)
if __name__ == "__main__":
print(Anagram("Antigone"))
print(Anagram("Fr. Inge C. Sonst, Rheine"))
print(Anagram("Ich sollte ein Anagram sein.", 2))
#Eismaschinen Alligatoren :mrgreen:
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 18:29
von EyDu
Xynon1 hat geschrieben:So, noch jemand verbesserungsvorschläge ?
Als erstes solltest du die überflüssige Klasse loswerden.
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 19:05
von Xynon1
Stimmt, mach ich halt ein def aus dem class

Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 21:05
von microkernel
Ist ecuh mal agfuefaleln das es eagl ist wie die bcsbuahetn zihwcesn den etersn und ltetzen wrot agnabhrcet snid? der mecsnh knan den txet todetrm lseen.

(könnte man doch auch mal programmieren

)
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 21:25
von nomnom
Hat mich mal interessiert:
Code: Alles auswählen
# Python 2
import random
import sys
text = raw_input("Dein Text: ")
for word in text.split():
sys.stdout.write(word[0])
for char in random.sample(word[1:-1], len(word[1:-1])):
sys.stdout.write(char)
sys.stdout.write(word[-1] + ' ')
print
Mir ist klar dass das extrem blöd gemacht ist

Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 21:32
von Xynon1
Das ist nun nhict scineodrlh swhecr aber hat jaemnd eine Iede wie man am bseten die Steezaizchn wieder hin bmkoemt ?
@nomnom
Meins ist auch nicht besser
Code: Alles auswählen
def shuffle(text):
list_ = []
for word in text.split():
mod = list(word.translate(string.maketrans("",""), string.punctuation))
shuffle_text = mod[1:-1]
random.shuffle(shuffle_text)
list_.append(mod[0] + "".join(shuffle_text) + mod[-1])
return " ".join(list_)
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 21:36
von nomnom
Steezaizchn
Wie?!
Ich hab grade nochmal das ganze geschrieben, diesmal Python 3:
Code: Alles auswählen
import random
def scramble_word(word):
scrambled_word = word[0]
for char in random.sample(word[1:-1], len(word[1:-1])):
scrambled_word += char
scrambled_word += word[-1]
return scrambled_word
text = input("Dein Text: ")
for word in text.split():
if len(word) < 2:
print(word, end=' ')
continue
print(scramble_word(word), end=' ')
print()
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 21:43
von ms4py
Xynon1 hat geschrieben:So, noch jemand verbesserungsvorschläge ?
Du solltest das Dictionary auf jeden Fall nur einmal laden, ist ja das selbe für jedes Anagram...
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 22:09
von Xynon1
Ja, habe ich schon erledigt, trotzdem danke.
Noch iwelche Ideen ?
Ich denke die Flaschenhälse hängen in der "text_for_anagram"-Funktion und der "combine_words"-Funktion bei den Kombinationen, fällt dort jemanden noch eine Optimierung ein.
Wenn ihr eine kleine Dokumentation dazu braucht, um zu verstehen was ich dort umsetzen wollte, müsst ihr es nur sagen.
Re: Anagramm-Generator
Verfasst: Donnerstag 2. Dezember 2010, 22:16
von EyDu
Hallo.
Raten wo der Flaschenhals ist bringt in den meisten Fällen nichts. Du solltest einfach messen, welcher Teil deines Codes wie lange braucht und dann optimieren.
Sebastian
Re: Anagramm-Generator
Verfasst: Freitag 3. Dezember 2010, 09:53
von Xynon1
Ich habe ja nicht direkt geraten, sondern dadurch das ich print anweisungen dazwischen gesetzt hatte, gesehen wo es länger dauert.
Aber ja ich kann nochmal genau nachmessen.
Dennoch sind ca. 80% oder mehr der Ausführungszeit bei den Kombinationen der einzelnen Wörter.
Dies geht ja auch schon aus dem Algorithmus heraus. Hat hier jemand noch eine Idee, wie man diese Kombination etwas besser handhaben kann ?
Edit: So habe es jetzt auch nochmal gemessen, bei "anagram("Ich sollte ein Anagram sein.", 2)" brauche ich für die ganze Funktion ca. 102 s.
Davon beträgt die "text_for_anagram" Funktion ca 5 s.
Fast der gesamte Rest geht an die "combine_words"-Funktion verloren mit ca. 97 s.
Edit2: Ich prüf jetzt nochmal extra auf die Länge, wie ich das zuvor schon gemacht hatte,
damit liegt die "combine_words"-Funktion nun bei 11s.
Trotzdem wäre ich noch an Verbesserungsvorschlägen interessiert.
So sieht es aktuell aus, ist jetzt auch schon etwas schneller
Code: Alles auswählen
from collections import defaultdict
import string
import itertools
SOURCE = "../dict/ngerman"
WORDS = defaultdict(list)
_dummy_table = string.maketrans("", "")
_delete_chars = string.punctuation + string.whitespace
def sort_word(word):
return "".join(sorted(word.translate(_dummy_table, _delete_chars).lower()))
def text_for_anagram(anagram):
for word in WORDS:
chars = list(word)
for char in anagram:
if char in chars:
del chars[chars.index(char)]
if len(chars) == 0:
yield word
def combine_words(anagram, combinations, max_words):
#Edit
length = len(anagram)
#
for combination in itertools.combinations(combinations, max_words):
#Edit2
word_combination = "".join(combination)
if len(word_combination) != length:
continue
#
if anagram == "".join(sorted("".join(word_combination))):
words = itertools.product(*[x for x in (WORDS.get(word) for word in
combination)])
for word in words:
yield " ".join(word)
def anagram(anagram="Fr. Inge C. Sonst, Rheine", max_words=1):
sorted_anagram = sort_word(anagram)
if max_words > 1:
combinations = list(text_for_anagram(anagram))
cw = combine_words(sorted_anagram, combinations, max_words)
result = "\n".join(cw)
else:
result = WORDS.get(sorted_anagram, "No anagram found.")
return "{0}: {1}".format(anagram, result)
if __name__ == "__main__":
with open(SOURCE) as lines:
for line in lines:
word = line.strip()
WORDS[sort_word(word)].append(word)
print(anagram("Antigone"))
print(anagram("Fr. Inge C. Sonst, Rheine"))
print(anagram("Ich sollte ein Anagram sein.", 2))
Re: Anagramm-Generator
Verfasst: Freitag 3. Dezember 2010, 12:18
von ms4py
Deine `text_for_anagram` Funktion ist mir noch unklar, was genau gibt die zurück?
IMO ist das das gleiche wie `WORDS[sort_word(anagram)]`