012
25.02.2005, 00:38 Uhr
NemoEimi
|
| Zitat von ~Kaiser: |
ich habe eine Buchstabenfolge von 25 Buchstaben, diese sind wahllos durcheinander
gemischt. In der richtigen Reihenfolge sollen sie einen deutschen Satz ergeben.
|
Hier mal ein Lösungsansatz dazu in Python, schnell zusammengeschraubt, äußerst ineffizient und mit überaus optimierungsbedürftigem Ausgabeverhalten  :
| Code: |
def prime(n):
if (n >= 2 and n <= 3):
return True
k = 3
if (n%2 == 0 or n < 2): return False
while (k*k <= n):
if (n%k == 0):
return False
k = k + 2
return True
smallprimes = filter(prime, range(3,200,2))
alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
enc = zip(alphabet, smallprimes)
encoder = dict(enc)
def normalform(wort):
p = 1
for buchstabe in wort:
p = p * encoder[buchstabe]
return p
datei = open('woerter.txt')
dateitext = datei.read()
dateitext = dateitext.upper()
woerter = dateitext.split()
woerter = filter(lambda(x): x.isalpha(), woerter)
lexlist = [(normalform(wort), wort) for wort in woerter]
lexikon = dict(lexlist)
def enthaelt(n):
def tmp_fun(pair):
k = pair[0]
return(n%k == 0)
return tmp_fun
def ent_rec(nf, liste, lex):
try:
loesung = liste + lexikon[nf]
print(loesung)
except KeyError:
for pair in lex:
k = pair[0]
if (nf%k == 0):
rest = nf/k
w = pair[1]
ent_rec(rest, liste + ' ' + w, filter(enthaelt(rest), lex))
def entschluessele_satz(satz):
nf = normalform(satz)
ent_rec(nf, 'Moegliche Wortliste:', lexlist)
|
Mit einem Testlexikon bestehend aus 25000 deutschen Wörtern (das ist die Datei "woerter.txt", die ich weiter oben öffne) findet das Programm leider für einen einfachen Testsatz eine sehr große Anzahl möglicher Zerlegungen in Wörter aus selbigem Lexikon. Es gäbe aber leichte Optimierungen, mit denen sich das (etwas) verbessern liesse.
Grüße,
Nemo
Dieser Post wurde am 25.02.2005 um 00:51 Uhr von NemoEimi editiert. |
