Python - Speed up generation of permutations of a list (and process of checking if permuations in Dict)

Question

I need a faster way to generate all permutations of a list, then check if each one is in a dictionary.

        for x in range (max_combo_len, 0, -1):
            possible_combos = []
            permutations = list(itertools.permutations(bag,x))
            for item in permutations:
                possible_combos.append(" ".join(item))
            #then check to see if each possible combo is in a specific Dict

If it helps, the lists are all going to be lists of strings. ['such as', 'this', 'one']

My solution works, but it's very slow. It could be that I need to stop using Python, but I thought I'd run it by you experts first!

Best, Gary

Answer 1

A very basic optimization:

permutations = list(itertools.permutations(bag,x))
for item in permutations:

can become...

for item in itertools.permutations(bag,x):

Answer 2

I can't test it very well without better input cases, but here are a few improvements:

for x in xrange(max_combo_len, 0, -1):
    possible_combos = (" ".join(item) for item in itertools.permutations(bag,x))
    #then check to see if each possible combo is in a specific Dict
    combos =  (c for c in possible_combos if c in specific_dict)

First, assuming you're using Python 2.x, xrange will help by not constructing an explicit list, but rather just yielding each x as you need it.

More importantly, you can throw the main effort into generator expressions and have it yield values on demand.

Answer 3

Something like this?

sentences = ['such as', 'this', 'ten eggs', 'one book', 'six eggs']
bag_of_words = set(['such', 'one','ten','book','eggs'])

possible = [sentence
            for sentence in sentences
            if all(word in bag_of_words for word in sentence.split())
            ]

print 'Possible to produce from bag words are:\n\t%s' % '\n\t'.join(possible)

Answer 4

    for x in xrange(max_combo_len, 0, -1):
        for item in itertools.permutations(bag,x):
            combo = " ".join(item)
            if combo in specificDict:
                yield combo

This way you don't have any large (and getting larger) lists, you just yield the passing comobs out of the function.

Answer 5

you can get rid of the many usesless (thrown away) join operations, if you prepare your special dict: just split the values or the keys, depending what you compare. This assumes of course that the dict is smaller than the number of all combos.

If you need the join, you have to slightly alter this. I think without you being more descriptive the problem isn't any better optimizable than this. And it's not gonna be much faster just by using another language.

(filtered_combo for filtered_combo in      
        itertools.chain.from_iterable(
                combo for combo in (itertools.permutations(bag, x) 
                        for x in xrange(max_combo_len, 0, -1)))
        if filtered_combo in special_dict)