8

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

4

5 回答 5

5

A very basic optimization:

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

can become...

for item in itertools.permutations(bag,x):
于 2010-09-22T06:03:50.533 回答
1

如果您准备特殊的字典，您可以摆脱许多无用（丢弃）的连接操作：只需拆分值或键，具体取决于您比较的内容。这当然假设字典小于所有组合的数量。

如果你需要加入，你必须稍微改变它。我认为如果没有您更具描述性，问题就没有比这更好的可优化性了。仅仅使用另一种语言也不会快得多。


(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)
于 2010-09-22T08:36:52.820 回答
1 
    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

这样你就没有任何大的（越来越大的）列表，你只需要从函数中产生传递的组合。

于 2010-09-22T07:26:06.400 回答
1

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.

于 2010-09-22T06:05:00.493 回答
0

像这样的东西？

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)
于 2010-09-22T06:29:07.313 回答