3

リストの一意の順列を探しています x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX "] 9 のグループで

私が現在していることは

from itertools import permutations
x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX"]
combos = []
for i in permutations(x, 9):
    if i not in combos:
        combos.append(i)
print combos

ただし、これは実行に時間がかかりすぎるため、誰かがより効率的なソリューションを提供してくれるかどうか疑問に思っていました.

4

3 に答える 3

7

if i not in combos:リスト内のメンバーシップ テストは (最悪の場合) O(N) であるため、長い時間がかかります。各要素をスキャンする必要があります。set代わりにa を使用できます。

>>> from itertools import permutations
>>> x = ["$5", "$10", "$10", "TAX", "$5", "20%", "BOGO", "BOGO", "TAX", "BOGO"]
>>> %time p = set(permutations(x, 9))
CPU times: user 0.88 s, sys: 0.01 s, total: 0.90 s
Wall time: 0.90 s
>>> len(p)
75600
于 2013-03-23T21:33:05.773 に答える
1

高速なセット構造を使用することに関する提案は適切ですが、最初から必要のないアイテムを生成しないと、最良の結果が得られます。の少し異なる表現をしてみましょうx:

from collections import OrderedDict
x = OrderedDict([("$5", 2), ("$10", 2), ("TAX", 2), ("20%", 1), ("BOGO", 3)])

次に、次の関数は、繰り返しのない順列を取得する必要があります。

from copy import copy
def permutations_unique(x, curr_list=[]):
    if not x:
        yield curr_list
        return
    last_item = None
    if curr_list:
        last_item = curr_list[-1]
    for item in x:
        if item != last_item:
            for j in range(1, x[item] + 1):
                xchild = copy(x)
                xchild[item] -= j
                if xchild[item] == 0:
                    del xchild[item]
                for y in permutations_unique(xchild, curr_list + [item] * j):
                    yield y

それは再帰です。各ステップで、項目と繰り返し回数を選択します。さらに、再帰の次のレベルで同じアイテムを選択することを避けます。

問題のインスタンスでは、このコードはset. x = [1] * 30ただし、反例を試してみてください。

于 2013-03-23T21:44:17.160 に答える
0

実行に時間がかかる理由は、要素をリストに追加すると、(平均して) リストの半分を検索する必要があるため、各検索に時間がかかるためです。より良いアプローチは、辞書を使用することです。

combos = {}

と：

if i not in combos:
    combos[i] = None # Just to put something there unless you need to store a value

これは、ハッシュ マップのルックアップ パフォーマンスを利用します。

メンバーシップ テストを行っているだけの場合は、DSM が推奨するセットを使用してください。

于 2013-03-23T21:32:37.630 に答える