Сколько общих английских слов из 4 или более букв вы можете сделать из букв данного слова (каждую букву можно использовать только один раз)

Question

На обратной стороне календаря блоков я нашел следующую загадку:

Сколько общих английских слов из 4 или более букв вы можете сделать из букв слова «учебник» (каждую букву можно использовать только один раз).

Мое первое решение, которое я придумал, было:

from itertools import permutations

with open('/usr/share/dict/words') as f:
    words = f.readlines()

words = map(lambda x: x.strip(), words)

given_word = 'textbook'

found_words = []

ps = (permutations(given_word, i) for i in range(4, len(given_word)+1))

for p in ps:
    for word in map(''.join, p):
        if word in words and word != given_word:
            found_words.append(word)
print set(found_words)  

Это дает результат set(['tote', 'oboe', 'text', 'boot', 'took', 'toot', 'book', 'toke', 'betook']), но на моей машине это заняло более 7 минут.

Моя следующая итерация была:

with open('/usr/share/dict/words') as f:
    words = f.readlines()

words = map(lambda x: x.strip(), words)

given_word = 'textbook'

print [word for word in words if len(word) >= 4 and sorted(filter(lambda letter: letter in word, given_word)) == sorted(word) and word != given_word]

которые возвращают ответ почти сразу, но дают ответ: ['book', 'oboe', 'text', 'toot']

Какое самое быстрое, правильное и наиболее питоническое решение этой проблемы?

( edit : добавлено мое более раннее решение перестановок и другой вывод).

Answer 1

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

Мы делаем небольшую предварительную обработку для ускорения вычислений.Основной подход заключается в следующем: мы присваиваем каждой букве алфавита простое число.Например, A = 2, B = 3 и так далее.Затем мы вычисляем хеш для каждого слова в алфавите, который является просто произведением простых представлений каждого символа в слове.Затем мы сохраняем каждое слово в словаре, индексируемом хэшем.

Теперь, если мы хотим выяснить, какие слова эквивалентны слову textbook, нам нужно только вычислить тот же хеш для слова и найти егов нашем словаре.Обычно (скажем, в C ++) нам приходится беспокоиться о переполнениях, но в python это даже проще: каждое слово в списке с таким же индексом будет содержать точно такие же символы.

Вот код снебольшая оптимизация, что в нашем случае нам нужно беспокоиться только о символах, которые также встречаются в данном слове, что означает, что мы можем обойтись гораздо меньшей таблицей простых чисел, чем в противном случае (очевидная оптимизация будет заключаться в назначении только тех символов, которые появляются в словезначение вообще - это было достаточно быстро, так что я не стал беспокоиться, и таким образом мы могли предварительно обработать только один раз и сделать это для нескольких слов).Первичный алгоритм достаточно полезен, так что вы все равно должны его использовать;)

from collections import defaultdict
from itertools import permutations

PRIMES = list(gen_primes(256)) # some arbitrary prime generator

def get_dict(path):
    res = defaultdict(list)
    with open(path, "r") as file:
        for line in file.readlines():
            word = line.strip().upper()
            hash = compute_hash(word)
            res[hash].append(word)
    return res

def compute_hash(word):
    hash = 1
    for char in word:
        try:
            hash *= PRIMES[ord(char) - ord(' ')]
        except IndexError:
            # contains some character out of range - always 0 for our purposes
            return 0
    return hash

def get_result(path, given_word):
    words = get_dict(path)
    given_word = given_word.upper()
    result = set()
    powerset = lambda x: powerset(x[1:]) + [x[:1] + y for y in powerset(x[1:])] if x else [x]
    for word in (word for word in powerset(given_word) if len(word) >= 4):
        hash = compute_hash(word)
        for equiv in words[hash]:
            result.add(equiv)
    return result

if __name__ == '__main__':
    path = "dict.txt"
    given_word = "textbook"
    result = get_result(path, given_word)
    print(result)

Запускается в моем списке слов Ubuntu (98k слов) довольно быстро, но не то, что я бы назвал Pythonic, так как это в основномпорт алгоритма c ++.Полезно, если вы хотите сравнить более одного слова таким образом ..

Answer 2

Как насчет этого?

from itertools import permutations, chain

with open('/usr/share/dict/words') as fp:
    words = set(fp.read().split())

given_word = 'textbook'

perms = (permutations(given_word, i) for i in range(4, len(given_word)+1))
pwords = (''.join(p) for p in chain(*perms))
matches = words.intersection(pwords)

print matches

, что дает

>>> print matches
set(['textbook', 'keto', 'obex', 'tote', 'oboe', 'text', 'boot', 'toto', 'took', 'koto', 'bott', 'tobe', 'boke', 'toot', 'book', 'bote', 'otto', 'toke', 'toko', 'oket'])

Answer 3

Следующее просто проверяет каждое слово в словаре, чтобы увидеть, имеет ли оно соответствующую длину, а затем, если это перестановка «учебник». Я позаимствовал проверку перестановки у Проверка, являются ли две строки перестановками друг друга в Python но немного изменил.

given_word = 'textbook'

with open('/usr/share/dict/words', 'r') as f:
    words = [s.strip() for s in f.readlines()]

matches = []
for word in words:
    if word != given_word and 4 <= len(word) <= len(given_word):
        if all(word.count(char) <= given_word.count(char) for char in word):
            matches.append(word)
print sorted(matches)

Это заканчивается почти сразу и дает правильный результат.

Answer 4

Создайте весь набор мощности, затем проверьте, находится ли словарное слово в наборе (порядок букв не имеет значения):

powerset = lambda x: powerset(x[1:]) + [x[:1] + y for y in powerset(x[1:])] if x else [x]

pw = map(lambda x: sorted(x), powerset(given_word))
filter(lambda x: sorted(x) in pw, words)

Answer 5

Есть генератор itertools.permutations, с помощью которого вы можете собрать все перестановки последовательности указанной длины. Это облегчает:

from itertools import permutations

GIVEN_WORD = 'textbook'

with open('/usr/share/dict/words', 'r') as f:
    words = [s.strip() for s in f.readlines()]

print len(filter(lambda x: ''.join(x) in words, permutations(GIVEN_WORD, 4)))

Редактировать # 1: О! Там написано "4 или больше";) Забудь, что я сказал!

Редактирование # 2: Это вторая версия, которую я придумал:

LETTERS = set('textbook')

with open('/usr/share/dict/words') as f:
    WORDS = filter(lambda x: len(x) >= 4, [l.strip() for l in f])

matching = filter(lambda x: set(x).issubset(LETTERS) and all([x.count(c) == 1 for c in x]), WORDS)
print len(matching)

Answer 6

Перестановки становятся очень большими для длинных слов.Попробуйте контрреволюционный например.

Я бы отфильтровал слова для слов от 4 до len (слово) (8 для учебника).Тогда я бы отфильтровал с регулярным выражением "гобой" .matches ("[учебник] +").

Остальные слова я бы отсортировал и сравнил с отсортированной версией вашего слова ("beoo", "bekoottx") с переходом на следующий индекс соответствующего символа, чтобы найти несовпадающие числасимволы:

("beoo", "bekoottx") 
("eoo", "ekoottx") 
("oo", "koottx") 
("oo", "oottx") 
("o", "ottx") 
("", "ttx") => matched


("bbo", "bekoottx") 
("bo", "ekoottx") => mismatch

Поскольку я не говорю на питоне, я оставляю реализацию в качестве упражнения для аудитории.