рекурсивная функция для поиска слов

Question

заданных букв: пример букв

letters = 'hutfb' 

Мне дан файл со списком слов.

Мне нужно написать рекурсивную функцию, которая позволяет мне проверять все возможностиписьма могут сделать.Если такая возможность есть в списке слов из файла, мне нужно напечатать это конкретное слово.

поэтому для заданных букв

они могут создавать слова:

• a
• cat
• ac
• act
• cab

и т. Д. И т. П.

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

Я не знаю, как начать писать эту функцию.

Answer 1

Я согласен с @dparolin относительно обработки файла слов, чтобы увидеть, соответствуют ли слова буквам, не генерировать возможные слова и посмотреть, есть ли они в файле.Это позволяет нам не читать файл в память, так как нам нужно проверять только одно слово за раз.И это можно сделать с помощью рекурсивного теста:

letters = 'catbt'

def is_match(letters, word):

    if not word:
        return True

    if not letters:
        return False

    letter = letters.pop()

    if letter in word:
        word.remove(letter)

    return is_match(letters, word)

with open('words.txt') as words:
    for word in words:
        word = word.strip()

        if is_match(list(letters), list(word)):
            print(word)

ПРИМЕР ИСПОЛЬЗОВАНИЯ

% python3 test.py
act
at
bat
cab
cat
tab
tact
%

И мы должны иметь возможность работать с большим количеством писем без проблем.

Answer 2

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

[EDIT] Убрана сортировка, поскольку она не дает никаких преимуществ, исправлена ​​ошибка, из-за которой я ложно устанавливал значение true на итерации

# Some letters, separated by space
letters = 'c a t b'
# letters = 't t a c b'

# # Assuming a word per line, this is the code to read it
# with open("words_on_file.txt", "r") as words:
#     words_to_look_for = [x.strip() for x in words]
#     print(words_to_look_for)

# Alternative for quick test
known_words = [
    'cat',
    'bat',
    'a',
    'cab',
    'superman',
    'ac',
    'act',
    'grumpycat',
    'zoo',
    'tab'
]

# Create a list of chars by splitting
list_letters = letters.split(" ")

for word in known_words:
    # Create a list of chars
    list_word = list(word)
    if len(list_word) > len(list_letters):
        # We cannot have longer words than we have count of letters
        # print(word, "too long, skipping")
        continue

    # Now iterate over the chars in the word and see if we have
    # enough chars/letters
    temp_letters = list_letters[:]

    # This was originally False as default, but if we iterate over each
    # letter of the word and succeed we have a match
    found = True
    for char in list_word:
        # print(char)
        if char in temp_letters:
            # Remove char so it cannot match again
            # list.remove() takes only the first found
            temp_letters.remove(char)
        else:
            # print(char, "not available")
            found = False
            break

    if found is True:
        print(word)

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

def product(*args, repeat=1):
    # product('ABCD', 'xy') --> Ax Ay Bx By Cx Cy Dx Dy
    # product(range(2), repeat=3) --> 000 001 010 011 100 101 110 111
    pools = [tuple(pool) for pool in args] * repeat
    result = [[]]
    for pool in pools:
        result = [x+[y] for x in result for y in pool]
    for prod in result:
        yield tuple(prod)

Answer 3

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

letters = ['a', 'b', 'c']

def powerset(letters):
    output = [set()]
    for x in letters:
        output.extend([y.union({x}) for y in output])
    return output

for subset in powerset(letters):
    for potential_word in map(''.join, itertools.permutations(list(subset))):
        # Check if potential_word is a word

Это не будет пытаться использовать слова с повторяющимися буквами (это будет еще один уровень безумия), но оно будет использовать все возможные возможности.слова, которые могут быть образованы подмножеством букв, которые вы даете в любом порядке.

[править] Просто понял, что вы запросили рекурсивное решение.Не знаю, требуется ли это или нет, но функция powerset может быть изменена на рекурсивную.Я думаю, что это сделало бы это более уродливым и трудным для понимания, хотя.

Answer 4

import itertools
str = "c a t b"
letters = list(str.replace(" ",""))
words_to_look_for = []

for index, letter in enumerate(letters):
    keywords = [''.join(i) for i in itertools.product(letters, repeat = index+1)]
    words_to_look_for.extend(keywords)

print(words_to_look_for)

/7299237/kakov-nailuchshii-sposob-sozdat-vse-vozmozhnye-trehbukvennye-stroki....