いくつかの基準に一致するアイテムのすべての組み合わせ（サイズ制限の下、この場合は8）を見つけるコードがいくつかありますが、コレクションサイズが約20アイテムになると、非常に遅くなります。コードの簡略版は次のとおりです。
from itertools import chain, combinations
import timeit
def powerset(iterable, n):
"powerset([1,2,3]) --> () (1,) (2,) (3,) (1,2) (1,3) (2,3) (1,2,3)"
s = list(iterable)
mx = min(len(s), n)
return chain.from_iterable(combinations(s, r) for r in range(1, mx+1))
collection = [
(0, 10, "item1"),
(5, 5, "item2"),
(10, 0, "item3"),
]
targetA = 5
targetB = 5
def build():
output = []
for s in powerset(collection, 8):
a, b = (0, 0)
for item in s:
a += item[0]
b += item[1]
if a >= targetA and b >= targetB:
output.append(s)
return output
print(timeit.timeit('build()', number=100, globals=globals()))
私の元のコードはアイテムにクラスを使用しており、コレクションが大きいため、任意の値よりも大きい値または小さい値の両方を検索できる必要があります。これは単なるブルートフォース検索であることは知っていますが（これはO(n!)それに近いか、それに近いと思います）、最適化できる方法はありますか？現在、アルゴリズムの複雑さについても学びながら、いくつかの基本的なアイデアを探しているだけなので、アドバイスを歓迎します。
独自の再帰関数を記述して、ターゲット値をパラメーターとして渡すことができます。このようにして、不足している量と残りのアイテムで達成可能な最大量を決定し、組み合わせが不可能になった場合に早期に停止することができます。
def combs_with_sum(collection, num, targetA, targetB):
def _inner(i, n, s):
# found a valid combination with n elements?
sum_a = sum(c[0] for c in s)
sum_b = sum(c[1] for c in s)
if n == 0 and sum_a >= targetA and sum_b >= targetB:
yield s
# more elements to go and still valid solutions?
max_a = sum(sorted(c[0] for c in collection[i:])[-n:])
max_b = sum(sorted(c[1] for c in collection[i:])[-n:])
if n > 0 and i < len(collection) and sum_a + max_a >= targetA and sum_b + max_b >= targetB:
# combinations without and with the current element
yield from _inner(i+1, n, s)
yield from _inner(i+1, n-1, s + [collection[i]])
return (x for n in range(1, num+1) for x in _inner(0, n, []))
ここでsum_a >= targetA and sum_b >= targetBは、有効な結果のみが生成されることを確認し、sum_a + max_a >= targetA and sum_b + max_b >= targetB実行不可能な組み合わせが検索されないようにします。これにより、各ターンでコレクションがスライス、ソート、および再度スライスされ、残りの要素で達成可能な最大の合計が見つかりますが、これにより、大量のブランチが検索されなくなります。（sum_aとのsum_b値をパラメーターとして渡すこともできますが、それはそれほど重要ではありません。）「より小さい」場合は、>=to<=を反転し、並べ替えを逆にして、n残りの最小項目の合計を取得します。
いくつかのランダムなテストデータに適用：
from random import randint, seed
seed(0)
collection = [(randint(1, 10), randint(1, 10), i) for i in range(20)]
print(collection)
res = list(combs_with_sum(collection, 4, 30, 30))
これにより_inner、sum_a + max_a ...チェックなしで15,000回を超える（つまり、すべての組み合わせをテストする）のに対して、1,000回未満の関数が呼び出されます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加