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

    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.