Найти слово максимальной длины из произвольных букв

Question

У меня 10 произвольных букв, и мне нужно проверить соответствие максимальной длины из файла слов

1. Я только недавно начал изучать RE, но не могу найти подходящий образец

   • Первой идеей было использование set: [10 символов], но оно также повторяет включенные символы, и я не знаю, как этого избежать

2. Я начал изучать Python недавно, но до RE и, возможно, RE не нужен, и это можно решить без него

   • использование «для этого в том:» итератор кажется неуместным, но, возможно, itertools может сделать это легко (с чем я не знаком)

Полагаю, решение известно даже начинающим программистам / сценаристам, но не мне Спасибо

Answer 1

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

Хитрость заключается в эффективной проверке каждого символа каждого слова в вашем файле слов на соответствие с набором из ваших исходных букв. Для каждого символа, если он найден в наборе тестов, удалите его из набора тестов и продолжайте; в противном случае слово не совпадает, и переходите к следующему слову.

Python имеет приятную функцию all для тестирования набора условий, основанных на элементах последовательности. all имеет дополнительную функцию, которая будет «замыкать», то есть, как только один элемент не выполнит условие, тесты больше не будут выполняться. Поэтому, если ваша первая буква в слове-кандидате - «z», а в исходных буквах нет «z», то нет смысла проверять больше букв в слове-кандидате.

Мой первый шанс написать это был просто:

matches = []
for word in wordlist:
    testset = set(letters)
    if all(c in testset for c in word):
        matches.append(word)

К сожалению, здесь ошибка в том, что если исходные буквы содержат одну букву «m», слово с несколькими буквами «m» будет ошибочно совпадать, поскольку каждая буква «m» будет отдельно соответствовать данной букве «m» в исходном тестовом наборе. Поэтому мне нужно было убрать каждую букву в том виде, в каком она была найдена.

Я воспользовался тем фактом, что set.remove(item) возвращает None, который Python рассматривает как логическое False, и расширил выражение моего генератора, используемое при вызове all. Для каждого слова в слове, если оно найдено в наборе тестов, я хочу дополнительно удалить его из набора тестов, например, (псевдокод, недопустимый Python):

all(c in testset and "remove c from testset" for c in word)

Поскольку set.remove возвращает None, я могу заменить приведенный выше бит на «not testset.remove (c)», и теперь у меня есть допустимое выражение Python:

all(c in testset and not testset.remove(c) for c in word)

Теперь нам просто нужно обернуть это в цикл, который проверяет каждое слово в списке (обязательно проверяйте новый набор тестов перед проверкой каждого слова, так как наш all тест теперь стал разрушительным тестом):

for word in wordlist:
    testset = set(letters)
    if all(c in testset and not testset.remove(c) for c in word):
        matches.append(word)

Последний шаг - сортировка совпадений по убыванию длины. Мы можем передать ключевую функцию для сортировки. Встроенный len был бы хорош, но это будет сортировать по возрастанию длины. Чтобы изменить его на нисходящий, мы используем лямбду, чтобы дать нам не len, а -1 * len:

matches.sort(key=lambda wd: -len(wd))

Теперь вы можете просто распечатать самое длинное слово в совпадениях [0] или перебрать все совпадения и распечатать их.

(Я был удивлен, что этот метод грубой силы работает так хорошо. Я использовал список слов 2of12inf.txt, содержащий более 80 000 слов, и для списка из 10 символов я получаю список совпадений примерно через 0,8 секунды на мой маленький 1.99GHz ноутбук.)

Answer 2

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

Вы можете хранить свои 10 произвольных букв в диктовке вместе с частотой, с которой они встречаются.

Например, ваши 4 (используя 4 вместо 10 для простоты) произвольные буквы: e, w, l, l.Это будет указано в следующем выражении: {'e': 1, 'w': 1, 'l': 2}

Затем для каждого слова в текстовом файле посмотрите, все ли буквы для этогоСлово может быть найдено в вашем диктанте произвольных букв.Если это так, то это одно из ваших слов-кандидатов.

Итак: мы хорошо выложим

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

Answer 3

Я думаю, этот код будет делать то, что вы ищете:

>>> words = open('file.txt')
>>> max(len(word) for word in set(words.split()))

Если вам требуется более сложный токенизатор, например, если вы не используете латинский текст, следует использовать NLTK :

>>> import nltk
>>> words = open('file.txt')
>>> max(len(word) for word in set(nltk.word_tokenize(words)))