Эффективный способ найти анаграммы предложений из словаря?

Часть проблемы решил сам. Устранен антипаттерн for-if в коде генератора:

def generate(database, length,letters,curstring="",curdata=set()):
if len(curstring.replace(" ",""))>length:
    return set()
if len((curstring).replace(" ",""))==length:
    return curdata.union(set([curstring]))
t=countletters(curstring)
for i in ascii_lowercase:
    if t[i]>letters[i]:
        return set()
for i in database:
    t=countletters(curstring+i)
    test=0
    for j in ascii_lowercase:
        if t[j]>letters[j]:
            test=1
    if test: continue
    if sum(t.values())<=length:
        curdata=curdata.union(generate(database.difference(set([i])),length,letters,curstring+" "+i,curdata))
        database=database.difference(set([i]))
return curdata

Теперь это намного, намного быстрее, но все еще медленно, если словарь содержит десятки тысяч слов и/или если входная строка длинная.

Вот рекурсивный подход, реализующий древовидный подход, который я предложил в комментариях:

def frequencyDict(s):
    s = s.lower()
    d = {}
    for c in s:
        if c.isalpha():
            if c in d:
                d[c] += 1
            else:
                d[c] = 1
    return d

def canMake(w,fdict):
    d = frequencyDict(w)
    return all(d[c] <= fdict.get(c,0) for c in d)

def candidates(wlist,fdict):
    return [w for w in wlist if canMake(w,fdict)]

def anagrams(wlist,fdict):
    if len(wlist) == 0 or len(fdict) == 0:
        return "no anagrams"
    hits = []
    firstWords = candidates(wlist,fdict)
    if len(firstWords) == 0:
        return "no anagrams"
    for w in firstWords:
        #create reduced frequency dict
        d = fdict.copy() 
        for c in w:
            d[c] -= 1
            if d[c] == 0: del d[c]
        #if d is empty, the first word is also a the last word
        if len(d) == 0:
            hits.append(w)
        else:
            #create reduced word list
            rlist = [v for v in wlist if canMake(v,d)]
            tails = anagrams(rlist, d)
            if tails != "no anagrams":
                hits.extend(w + " " + t for t in tails)
    if len(hits) == 0:
        return "no anagrams"
    else:
        return hits

def findAnagrams(wlist,s):
    return anagrams(wlist,frequencyDict(s.lower()))

f = open("linuxwords.txt")
words = f.read().split('\n')
f.close()
words = [w.strip().lower() for w in words if not '-' in w]
test = findAnagrams(words, "Donald Trump")

Требуется около 20 секунд, чтобы найти все 730 анаграмм «Дональд Трамп», взятых из старого списка слов Linux. Мой любимый "Владыка сырого ореха"