python recursion: create all possible sentence of certain length using a key-value dictionary of word
<p>So, let's say we have a dictionary</p>

<pre><code>&gt;&gt;&gt; dictionary
{'and': ['the'], 'the': ['cat', 'dog'], 'cat': ['and']}
</code></pre>

<p>We want to create all possible sentences of certain length (say 5 in our case), where each sentence starts with a <code>key</code> in the dictionary followed by an element from it's values, then the chosen value becomes the key for next step (if the value is also in the set of keys) and so on until we hit the desired sentence length. </p>

<p>To elaborate, say, in one of the sentences( denote <code>s</code>) we are producing our first key is <code>and</code>, then it will be followed by <code>the</code> since <code>(and,the)</code> is key-value pair. So, now we have <code>s = "and the"</code>. While extending <code>s</code>, now we will use <code>the</code> as the key. We have two possible values for <code>the</code> that is <code>cat</code> and <code>dog</code>. So, from <code>s</code>, we have
<code>s1 = "and the cat"</code> and <code>s2 = "and the dog"</code>. Now, <code>dog</code> is not a <code>key</code> in the dictionary, so we cannot pursue this road anymore to achieve a sentence of length 5. So, we stop here. But we can continue for <code>s1</code> by extending it to <code>s1 = "and the cat and"</code> and so on...</p>

<p>For the given dictionary, we should get the following sentences:</p>

<pre><code>'and the cat and the',
'the cat and the dog',
'the cat and the cat', 
'cat and the cat and'
</code></pre>

<p>I am trying it with recursive backtracking like following:</p>

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

def recurse(split_sentence,key):
    if len(split_sentence) &gt;= 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"
</code></pre>

<p>But it's giving me output </p>

<pre><code>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
</code></pre>

<p>Could someone help me figure out where I am doing it wrong?</p>

<p>The problem is that you are modifying <code>split_sentence</code> in your loop around the recursive call; assigning it to another variable just means you have a new name for the same list.  Making a new list to make the recursive call with can be done like so:</p>

<pre><code>    for value in dictionary[key]:
        recurse(split_sentence+[value],value)
</code></pre>

python dictionary recursion dynamic-programming backtracking