时间戳

首页 > 解决方案 > 用于单词搜索的递归函数

python - 用于单词搜索的递归函数

问题描述

给定字母：字母示例

letters = 'hutfb'

我得到了一个包含单词列表的文件。

我需要编写一个递归函数来检查字母可以产生的所有可能性。如果可能在文件中的单词列表中，我需要打印该特定单词。

所以对于给定的字母

他们可以创造单词：

等等等等

这些字母的每个组合我都需要检查文件以查看它是否是有效的单词。如果是我需要打印它们。

我不知道如何开始编写这个函数。

标签： pythonpython-3.xfilerecursion

解决方案

不幸的是，我现在无法使用递归函数，但鉴于如果在创建过程中不过滤，更多的字母/字符很容易爆炸成数十亿个潜在组合，我有一个通过迭代已知单词的古怪替代方案。无论如何，这些都必须在内存中。

[编辑] 删除了排序，因为它并没有真正提供任何好处，修复了我在迭代时错误地设置为 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)

您可以从 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)

推荐阅读