递归是解决方案吗？Python

Question

我试图找出哪些单词可以用Mendeelev表拼写。例如，“helico”一词可以拼写为He-Li-Co（氦锂碳氧），也可以拼写为He-Li-Co（氦锂钴）。 我为此写了一个小程序。我在单词列表中有单词（“helico”、“cute”等），元素在元素中（“H He Li”…） 我使用了递归，因为我认为我可以接受一个单词，在单词的开头查找一个元素，删除它，然后用较短的单词重新启动过程。如果这个词最后是空的，就意味着它是可以拼写的。 这是可行的，但问题是，一旦我找到了第一个解决方案（He Li C O），我就很难回到下一个解决方案——He Li C O 因为递归性，“helico”变成了“co”，我会找到co，但是已经“忘记”了第一部分（何莉）

我的感觉是，因为每个单词可能有几个解决方案，所以递归不适合。你知道吗

有什么想法吗？我不是在寻找解决办法，而是想办法帮我解决这个问题。。。你知道吗

def search_element(startword, match):
    print startword," MATCH IS",match
    if startword =="":
        print match, "empty startword"
        match =""
    for elem in elements:
        #print elem,
        if elem == "$$":
            match =""
        if startword.startswith(elem):
            newword = startword.replace(elem,"",1)
            match = match +" "+ elem
            #print startword, elem, match, "----", newword
            match = search_element(newword, match)
    return(match)


elements = ['h', 'he', 'li', 'be', 'b', 'c', 'n', 'o', 'f', 'ne', 'na', 'mg', 'al', 'si', 'p', 's', 'cl', 'ar', 'k', 'ca', 'sc', 'ti', 'v', 'cr', 'mn', 'fe', 'co', 'ni', 'cu', 'zn', 'ga', 'ge', 'as', 'se', 'br', 'kr', 'rb', 'sr', 'y', 'zr', 'nb', 'mo', 'tc', 'ru', 'rh', 'pd', 'ag', 'cd', 'in', 'sn', 'sb', 'te', 'i', 'xe', 'cs', 'ba', 'la', 'ce', 'pr', 'nd', 'pm', 'sm', 'eu', 'gd', 'tb', 'dy', 'ho', 'er', 'tm', 'yb', 'lu', 'hf', 'ta', 'w', 're', 'os', 'ir', 'pt', 'au', 'hg', 'tl', 'pb', 'bi', 'po', 'at', 'rn', 'fr', 'ra', 'ac', 'th', 'pa', 'u', 'np', 'pu', 'am', 'cm', 'bk', 'cf', 'es', 'fm', 'md', 'no', 'lr', 'rf', 'db', 'sg', 'bh', 'hs', 'mt', 'ds', 'rg', 'cp', 'uut', 'uuq', 'uup', 'uuh', 'uus', 'uuo', '$$']
word_list =['helico', 'cute']


for word in word_list:
    match=""
    search_element(word, match)

Answer 1

这是递归的典型例子。下面是一个示例代码：

def findall(word, elements):
    def sub(word, res):
        if word:
            for elt in elements:
                if word.startswith(elt):
                    yield from sub(word[len(elt):], res+[elt])
        else:
            yield res
    yield from sub(word, [])

测试：

for word in word_list:
    for res in findall(word, elements):
        print(word, res)

收益率

helico ['he', 'li', 'c', 'o']
helico ['he', 'li', 'co']
cute ['c', 'u', 'te']
cute ['cu', 'te']

Answer 2

我认为递归非常适合这个问题。让我们暂时把Uu*元素放在一边，这样我们就有了一个和两个字母的块。可能的排列的数目随着单词的长度呈指数增长。10个字母的单词少于100个，20个字母的单词多于10000个。你知道吗

但是：你不必考虑所有这些可能性。如果使用递归，可以避免陷入死分支。假设您想返回一个组合列表。你知道吗

• 从原来的单词w开始
• 如果单词是空的：那么我们找到了一个字符串。你知道吗
• 第一个字母是有效的元素符号吗？保存w[1:]并用w[1:]递归
• 前两个字母是有效的元素符号吗？保存w[2:]并用w[2:]递归
• 将合并结果向上返回一级

当然，到目前为止，您必须想出一种存储结果的方法。例如，您可以在每个递归中构建一个带有连字符的字符串，并在递归命中空单词时返回一个仅包含该字符串的列表。你知道吗

这比生成所有组合然后检查它们是否是有效元素要好得多。我的示例实现在不到半秒钟的时间内拆分了一个大约50000个单词的字典。你知道吗

顺便说一下，您应该使用集合或字典而不是列表来存储元素符号。你知道吗