Geek Answers Handbook

Python - speed up the creation of permutations of a list (and the verification process if permutations in a dict)

I need a faster way to generate all the permutations of the list, and then check if each of them is in the 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 this helps, all lists will be line lists. [', for example', 'this', 'one']

My solution works, but it is very slow. Maybe I need to stop using Python, but I thought I started it with experts first!

Best, Gary

+4
source share
5 answers

I cannot verify this very well without the best input events, 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, if you use Python 2.x, xrange will help you by not building an explicit list, but simply by giving each x as needed.

More importantly, you can throw the main effort into the expressions of the generator and get the values ​​on demand.

+1
source

Very simple optimization:

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

can be...

 for item in itertools.permutations(bag,x):
+5
source 
  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

Thus, you do not have large (and more) lists, you just pass the missing combos from the function.

+1
source

you can get rid of many useless (discarded) union operations if you prepare your own special dict: just split the values ​​or keys, depending on what you are comparing. This suggests, of course, that the dict is less than the number of all combos.

If you need a connection, you need to change this a bit. I think that if you are not more visible, the problem will not be better optimized than this. And it won’t be much faster just using a different 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)
+1
source

Something like that?

 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)
0
source

More articles:


All Articles