hmi hmi - 2 months ago 8
Python Question

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

So, let's say we have a dictionary

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


We want to create all possible sentences of certain length (say 5 in our case), where each sentence starts with a
key
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.

To elaborate, say, in one of the sentences( denote
s
) we are producing our first key is
and
, then it will be followed by
the
since
(and,the)
is key-value pair. So, now we have
s = "and the"
. While extending
s
, now we will use
the
as the key. We have two possible values for
the
that is
cat
and
dog
. So, from
s
, we have
s1 = "and the cat"
and
s2 = "and the dog"
. Now,
dog
is not a
key
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
s1
by extending it to
s1 = "and the cat and"
and so on...

For the given dictionary, we should get the following sentences:

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


I am trying it with recursive backtracking like following:

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"


But it's giving me output

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


Could someone help me figure out where I am doing it wrong?

Answer

The problem is that you are modifying split_sentence 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:

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