Python - возможные английские анаграммы с одним словом, заданные входные буквы

Question

Я знаю, что варианты этого уже задавались, но я не смог понять ни одну из предыдущих реализаций, потому что большинство из них были связаны с использованием наборов и метода issubset.

Вот что я пытаюсь сделать: у меня есть набор слов в словаре и список возможных букв. Я хочу выяснить, могут ли члены набора быть сформированы путем перестановки букв в списке. Вот моя текущая реализация:

def solve(dictionary, letters):

    for word in dictionary: #for each word in the dictionary
        if len(word) > len(letters):   # first optimization, doesn't check words that are larger than letter set
            continue
        else: 
            scrambledword = "".join([b for b in sorted(list(word))]) #sorts the letters in each word
            if set(scrambledword).issubset(letters):
                print word


def main():
    dictionary = set([x.strip() for x in open("C:\\Python27\\dictionary.txt")])        
    letters = sorted(['v','r','o','o','m','a','b','c','d'])
    solve(dictionary, letters)


main()

Очевидная проблема с этой реализацией состоит в том, что будут найдены некоторые слова, которые используют более одной буквы в «букв». Например, слово «картон» отображается как допустимое слово, несмотря на то, что в списке букв есть только одна копия «а» и «г». Как я могу использовать метод issubset в списках?

Answer 1

Чтобы узнать, можете ли вы составить слово из набора букв [упс, я сделал это сам - я имел в виду «сбор»!], Вы хотите, чтобы каждая буква встречалась хотя бы нужное количество раз, поэтому яЯ думаю, что нам придется как-то работать там.По определению наборы Python не заботятся о количестве элементов в исходном списке.Может быть, что-то вроде

from collections import Counter

letters = ['v','r','o','o','m','a','b','c','d']
words = 'cardboard boom booom'.split()
letterscount = Counter(letters)

for word in words:
    wordcount = Counter(word)
    print word, all(letterscount[c] >= wordcount[c] for c in wordcount)

, дающее

cardboard False
boom True
booom False

Счетчик - полезный служебный класс:

>>> c = Counter(letters)
>>> c
Counter({'o': 2, 'a': 1, 'c': 1, 'b': 1, 'd': 1, 'm': 1, 'r': 1, 'v': 1})
>>> c['o']
2
>>> c['z']
0

[DSM: возвращение!Я удалил редактирование сообщества, которое не работает, потому что экземпляры Counter не могут быть хэшируемыми.]

Если скорость поиска важна, вы можете обменять память и время предварительного вычисления:

from collections import defaultdict, Counter
from itertools import combinations

# precomputations
allwords = open('/usr/share/dict/words').read().split() 
allwords = list(w for w in allwords if len(w) >= 3) # hack, /words contains lots of silliness
allwords_by_count = defaultdict(list)
for i, word in enumerate(allwords):
    allwords_by_count[frozenset(word)].append((word, Counter(word)))
    if i % 1000 == 0:
        print i, word


def wordsfrom(letters, words_by_count):
    lettercount = Counter(letters)
    for subsetsize in range(1, len(lettercount)+1):
        for subset in combinations(lettercount, subsetsize):
            for possword, posswordcount in words_by_count[frozenset(subset)]:
                if all(posswordcount[c] <= lettercount[c] for c in posswordcount):
                    yield possword

>>> wordsfrom('thistles', allwords_by_count)
<generator object wordsfrom at 0x1032956e0>
>>> list(wordsfrom('thistles', allwords_by_count))
['ess', 'sis', 'tit', 'tst', 'hei', 'hie', 'lei', 'lie', 'sie', 'sise', 'tie', 'tite', 'she', 'het', 'teth', 'the', 'els', 'less', 'elt', 'let', 'telt', 'set', 'sett', 'stet', 'test', 'his', 'hiss', 'shi', 'sish', 'hit', 'lis', 'liss', 'sil', 'lit', 'til', 'tilt', 'ist', 'its', 'sist', 'sit', 'shies', 'tithe', 'isle', 'sile', 'sisel', 'lite', 'teil', 'teli', 'tile', 'title', 'seit', 'sesti', 'site', 'stite', 'testis', 'hest', 'seth', 'lest', 'selt', 'lish', 'slish', 'hilt', 'lith', 'tilth', 'hist', 'sith', 'stith', 'this', 'list', 'silt', 'slit', 'stilt', 'liesh', 'shiel', 'lithe', 'shiest', 'sithe', 'theist', 'thesis', 'islet', 'istle', 'sistle', 'slite', 'stile', 'stilet', 'hitless', 'tehsil', 'thistle']

[Хех.Я только что заметил, что самого «чертополоха» нет в списке, но это потому, что его нет в файле слов ..]

И да, очевидные «не слова» действительно присутствуют в файле слов:

>>> assert all(w in allwords for w in (wordsfrom('thistles', allwords_by_count)))
>>> 

Answer 2

Если вы ищете анаграммы, другими словами, вы хотите переставить, но использовать их все (в отличие от использования только подмножества), тогда есть другое решение.

Сначала вы предварительно обработаете все слова всловарь.Для данного слова вы производите слово, написанное с теми же буквами, но в алфавитном порядке:

def alphabetize(word):
    "".join(sorted(word))

и помещаете эти новые слова в набор newDictionary Тогда ваша функция может вызывать алфавитную обработку букв и проверять,результат в словаре.

def solve(newDictionary, letters):
    query = alphabetize(letters)
    return query in newDictionary

Функция алфавита является характеристикой анаграмм: два слова являются анаграммами друг друга, если и только если они дают одинаковый результат, когда к ним применяется алфавит.

Answer 3

Импортируя collections, мы определяем хешируемый мультимножество:

def Letters(x):
    return frozenset(Counter(x).items())

Теперь мы предварительно обработали словарь в словаре -> {anagram1, anagram2, ...}:

vocabulary = ['apple', 'banana', 'rats', 'star', 'tars']
countsToWords = defaultdict(lambda: set())
for word in vocabulary:
    countsToWords[Letters(word)].add(word)

Ваша функция «решить» теперь занимает O (1) время:

def solve(query):
    return countsToWords[Letters(query)]

Пример:

print( solve('star') )
# {'tars', 'star', 'rats'}