Pythonの再帰：だから言葉

Question

のキーと値の辞書を使用して、特定の長さのすべての可能な文を作成し、（5を言うのは、我々は我々が一定の長さのすべての可能な文章を作成したい辞書

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

を持っているとしましょう私たちの場合）、各文はディクショナリのkeyで始まり、その値の要素が続き、次に選択された値が次のステップのキーになります（値がキーのセットに含まれている場合）。所望の文章の長さ。 （sを表す）我々は最初のキーを生産している文章の一つに、たとえば、手の込んだ

は(and,the)は、キーと値のペアであるので、それはtheが続く、andです。だから今はs = "and the"です。 sを拡張している間、今度はtheをキーとして使用します。 theには、catとdogの2つの値があります。したがって、sからは、 s1 = "and the cat"とs2 = "and the dog"があります。さて、dogは辞書の中でkeyではないので、私たちはこの道を追って長さ5の文を達成することはできません。そこでここでやります。しかし、我々は...ように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)