Код ниже использует рекурсивный генератор для построения решений. Для хранения целевых букв мы используем collections.Counter, это действует как набор, разрешающий повторяющиеся элементы.
Чтобы упростить поиск, мы создаем словарь для каждой требуемой длины слова, сохраняя каждый из этих словарей в словаре с именем all_words с длиной слова в качестве ключа. В каждом под-словаре хранятся списки слов, содержащих одинаковые буквы, с отсортированными буквами в качестве ключа, например, 'aet': ['ate', 'eat', 'tea'].
Я использую стандартный файл слов Unix '/ usr / share / dict / words'. Если вы используете файл в другом формате, вам может потребоваться изменить код, который помещает слова в all_words.
Функция solve начинает поиск с наименьшей длины слова и работает до самой большой. Это, вероятно, самый эффективный порядок, если набор, содержащий самые длинные слова, является самым большим, поскольку окончательный поиск выполняется путем простого поиска в dict, который очень быстр. Предыдущие поиски должны были проверить каждое слово в под-словаре этой длины, ища ключи, которые все еще находятся в целевой сумке.
#!/usr/bin/env python3
''' Create anagrams from a string of target letters and a list of word lengths '''
from collections import Counter
from itertools import product
# The Unix word list
fname = '/usr/share/dict/words'
# The target letters to use
target = 'lndjobeawrl'
# Word lengths, in descending order
wordlengths = [5, 4, 2]
# A dict to hold dicts for each word length.
# The inner dicts store lists of words containing the same letters,
# with the sorted letters as the key, eg 'aet': ['ate', 'eat', 'tea']
all_words = {i: {} for i in wordlengths}
# A method that tests if a word only contains letters in target
valid = set(target).issuperset
print('Scanning', fname, 'for valid words...')
count = 0
with open(fname) as f:
for word in f:
word = word.rstrip()
wlen = len(word)
# Only add words of the correct length, with no punctuation.
# Using word.islower() eliminates most abbreviations.
if (wlen in wordlengths and word.islower()
and word.isalpha() and valid(word)):
sorted_word = ''.join(sorted(word))
# Add this word to the list in all_words[wlen],
# creating the list if it doesn't exist
all_words[wlen].setdefault(sorted_word, []).append(word)
count += 1
print(count, 'words found')
for k, v in all_words.items():
print(k, len(v))
print('\nSolving...')
def solve(pos, bag, solution):
wlen = wordlengths[pos]
if pos == 0:
# See if the letters remaining in the bag are a valid word
key = ''.join(sorted(bag.elements()))
if key in all_words[wlen]:
yield solution + [key]
else:
pos -= 1
for key in all_words[wlen].keys():
# Test that all letters in key are in the bag
newbag = bag.copy()
newbag.subtract(key)
if all(v >= 0 for v in newbag.values()):
# Add this key to the current solution and
# recurse to find the next key
yield from solve(pos, newbag, solution + [key])
# Find all lists of keys that produce valid combinations
for solution in solve(len(wordlengths) - 1, Counter(target), []):
# Convert solutions to tuples of words
t = [all_words[len(key)][key] for key in solution]
for s in product(*t):
print(s)
выход
Scanning /usr/share/dict/words for valid words...
300 words found
5 110
4 112
2 11
Solving...
('ad', 'jell', 'brown')
('do', 'jell', 'brawn')
('ow', 'jell', 'brand')
('re', 'jowl', 'bland')
FWIW, вот результаты для
target = 'nobigword'
wordlengths = [4, 3, 2]
выход
Scanning /usr/share/dict/words for valid words...
83 words found
4 31
3 33
2 7
Solving...
('do', 'big', 'worn')
('do', 'bin', 'grow')
('do', 'nib', 'grow')
('do', 'bow', 'grin')
('do', 'bow', 'ring')
('do', 'gin', 'brow')
('do', 'now', 'brig')
('do', 'own', 'brig')
('do', 'won', 'brig')
('do', 'orb', 'wing')
('do', 'rob', 'wing')
('do', 'rib', 'gown')
('do', 'wig', 'born')
('go', 'bid', 'worn')
('go', 'bin', 'word')
('go', 'nib', 'word')
('go', 'bow', 'rind')
('go', 'din', 'brow')
('go', 'now', 'bird')
('go', 'own', 'bird')
('go', 'won', 'bird')
('go', 'orb', 'wind')
('go', 'rob', 'wind')
('go', 'rib', 'down')
('go', 'row', 'bind')
('id', 'bog', 'worn')
('id', 'gob', 'worn')
('id', 'orb', 'gown')
('id', 'rob', 'gown')
('id', 'row', 'bong')
('in', 'bog', 'word')
('in', 'gob', 'word')
('in', 'dog', 'brow')
('in', 'god', 'brow')
('no', 'bid', 'grow')
('on', 'bid', 'grow')
('no', 'big', 'word')
('on', 'big', 'word')
('no', 'bow', 'gird')
('no', 'bow', 'grid')
('on', 'bow', 'gird')
('on', 'bow', 'grid')
('no', 'dig', 'brow')
('on', 'dig', 'brow')
('or', 'bid', 'gown')
('or', 'big', 'down')
('or', 'bog', 'wind')
('or', 'gob', 'wind')
('or', 'bow', 'ding')
('or', 'wig', 'bond')
('ow', 'bog', 'rind')
('ow', 'gob', 'rind')
('ow', 'dig', 'born')
('ow', 'don', 'brig')
('ow', 'nod', 'brig')
('ow', 'orb', 'ding')
('ow', 'rob', 'ding')
('ow', 'rid', 'bong')
('ow', 'rig', 'bond')
Этот код был написан для Python 3. Вы можете использовать его на Python 2.7, но вам нужно будет изменить
yield from solve(pos, newbag, solution + [key])
до
for result in solve(pos, newbag, solution + [key]):
yield result