python 递归：使用单词的键值字典创建一定长度的所有可能的句子

Question

所以，假设我们有一本字典

>>> dictionary
{'and': ['the'], 'the': ['cat', 'dog'], 'cat': ['and']}

我们想创建所有可能的特定长度的句子（在我们的例子中是 5 个），其中每个句子在字典中以 key 开头，后跟它的值中的一个元素，然后选择的值变为下一步的键（如果该值也在键集中）等等，直到我们达到所需的句子长度。

详细说明，比如说，在其中一个句子中（表示 s），我们生成的第一个密钥是 and，然后是 the，因为 (and,the) 是键值对。所以，现在我们有 s = "and the"。在扩展 s 的同时，现在我们将使用 the 作为键。 the 有两个可能的值，即 cat 和 dog。所以，从 s，我们有 s1 = "and the cat" 和 s2 = "and the dog"。现在，dog 已经不是字典中的 key 了，所以我们不能再走这条路来实现长度为 5 的句子了。所以，我们就此打住。但是我们可以通过将 s1 扩展到 s1 = "and the cat and" 等来继续 s1...

对于给定的字典，我们应该得到以下句子：

'and the cat and the',
'the cat and the dog',
'the cat and the cat', 
'cat and the cat and'

我正在尝试使用递归回溯，如下所示：

dictionary = {'and': ['the'], 'the': ['cat', 'dog'], 'cat': ['and']}
sentence_list = []
sentence_length = 5

def recurse(split_sentence,key):
    if len(split_sentence) >= sentence_length:
        sentence_list.append(split_sentence)
        return
    elif key not in dictionary.keys():
        return
    else:
        for value in dictionary[key]:
            split = split_sentence
            split.append(value)
            recurse(split,value)
    return

for key in dictionary.keys():
    split_sentence = []
    recurse(split_sentence, key)


for elem in sentence_list:
    sentence = " ".join(elem)
    print sentence + "\n"

但它给了我输出

the cat and the cat dog dog

the cat and the cat dog dog

the cat and the cat dog dog

cat and the cat and dog dog

cat and the cat and dog dog

cat and the cat and dog dog

and the cat and the dog

and the cat and the dog

谁能帮我找出我哪里做错了？

Answer 1

问题是您在围绕递归调用的循环中修改 split_sentence；将它分配给另一个变量只意味着您为同一个列表有了一个新名称。可以像这样创建一个新列表来进行递归调用：

    for value in dictionary[key]:
        recurse(split_sentence+[value],value)

python 递归：使用单词的键值字典创建一定长度的所有可能的句子

python recursion: create all possible sentence of certain length using a key-value dictionary of word

python

recursion

dictionary

dynamic-programming

backtracking