Anagramm-Generator

[derdon]

Joa, hatte Langeweile: http://paste.pocoo.org/show/297798/

Beispielaufruf:

Code: Alles auswählen

./anagram_generator.py dog                         
dog
god

[EyDu]

Code: Alles auswählen

"".join
plain_words.__contains__

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

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

[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()

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

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

[ms4py]

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

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

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

[EyDu]

So, noch jemand verbesserungsvorschläge ?

Als erstes solltest du die überflüssige Klasse loswerden.

[Xynon1]

Stimmt, mach ich halt ein def aus dem class

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

[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

[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_)

[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()

[ms4py]

So, noch jemand verbesserungsvorschläge ?

Du solltest das Dictionary auf jeden Fall nur einmal laden, ist ja das selbe für jedes Anagram...

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

[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

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

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