Finding all sentences from list of keywords to dict

Question

I have list of possible words to make anagram of the given words. Each string of list is key to dictionary and has value of one or more words. Which is the best (fastest, pythonic) way to make all possible sentences in the order of the keys from the words in each list of the corresponding keys in the dictionary. Lists have variable number of keys in them.

keylist = ['key1', 'key2', 'key3']
worddict = {'key1': ['a','b','c'], 'key2':['d','e','f'], 'key3':['g','h','i']}

Expected result (first word from first keys list, second from second keys list and so on):

["a d g",
"a d h",
"a d i",
.....
"c f i"]

Answer 1

Does something like this work?

import itertools
anagrams = []
for x in itertools.product(*worddict.values()):
    anagrams.extend(" ".join(y) for y in itertools.permutations(x))

Answer 2

Use the product function in the itertools module to produce all combinations of your iterables

import itertools

for sentence in itertools.product(['a','b','c'], ['d','e','f'], ['g','h','i']):
    print sentence

The output will be tuples, but these can easily be converted to strings or lists if required.

Answer 3

Encouraged to monkey with the products I could bend them to adapt variable number of keys from dictionary of lists like this:

import itertools
keylist = ['key1', 'key4','key2']
worddict = {'key1': ['a','b','c'],
            'key2':['d','e','f'],
            'key3':['g','h','i'],
            'key4':['j','k','l']}
sentences = (' '.join(sentence)
             for sentence in itertools.product(*(worddict[k]
                                                 for k in keylist)))
print '\n'.join(sentences)