使用 itertools 将不同代币提名的组合汇总为目标值

Question

如果我有 3 种硬币（一、二和五）。我有不同数量的每种硬币。我怎样才能让所有组合都等于某个目标？

例如：

one = [1, 1, 1]  # 3 coins of 1
two = [2, 2]     # 2 coins of 2
five = [5, 5, 5] # 3 coins of 5
target = 10

使用此代码：

s = set()
one = 3
two = 2
five = 5

for c in combinations_with_replacement((0,1,1,1,2,2,5,5,5), 8):
    if sum(c) == target:
        s.add(c)

for c in s:
  if c.count(1) <= one and c.count(2) <= two and c.count(5) <= five:
    print(f"{c.count(1)} * one + {c.count(2)} * two + {c.count(5)}* five = 10")

给这些组合加上目标总和：

3 * one + 1 * two + 1 * five = 10
0 * one + 0 * two + 2 * five = 10
1 * one + 2 * two + 1 * five = 10

但是，我觉得这不是最好的方法，如何以更优雅的方式解决这个问题？问题是使用 itertools、collections 或其他模块来简化该任务。

没有嵌套 for 循环。

Answer 1

您需要使用 combinations 而不是 combinations_with_replacement，因此您的 count 检查可以省略。

另外，为什么只检查长度为 8 的组合？您应该检查从 0 到 len(all_coins) 的任何一个，这就是为什么 应该嵌套 for 循环 （查看所有可能组合的更多示例 here）

最终代码可能是：

import itertools

ones = [1, 1, 1]  # 3 coins of 1
twos = [2, 2]     # 2 coins of 2
fives = [5, 5, 5] # 3 coins of 5
target = 3

all_coins = ones + twos + fives

res = set()
for coins_to_take in range(len(all_coins)+1):
    for c in itertools.combinations(all_coins, coins_to_take):
        if sum(c) == target:
            res.add(c)

for r in res:
    print(r)

Answer 2

你可以使用 list comprehension 来隐藏事实，你真的 do 需要使用嵌套 for 循环来解决这个问题一般方式（避免可能必须对 非常大的 数字 non-nested 进行硬编码：

from itertools import chain, combinations

ones = [1, 1, 1]   # 3 coins of value 1
twos = [2, 2]      # 2 coins of value 2
fives = [5, 5, 5]  # 3 coins of value 5
all_coins = ones + twos + fives
target = 10

combos = set()
for combo in chain.from_iterable(combinations(all_coins, length)
                                    for length in range(1, len(all_coins)+1)):
    if sum(combo) == target:
        combos.add(combo)

print(combos)

您可以通过添加辅助函数以更易读的方式打印结果：

from itertools import groupby

denomination = {1: 'ones', 2: 'twos', 5: 'fives'}  # Names of values.

def ppcombo(combo):
    """ Pretty-print a combination of values. """
    groups, uniquekeys = [], []
    combo = sorted(combo)
    for key, group in groupby(combo):
        groups.append(list(group))
        uniquekeys.append(key)
    counts = {key: len(group) for key, group in zip(uniquekeys, groups)}
    print(' + '.join(f'{count}*{denomination[value]}' for value, count in counts.items()))

print('combos:', combos)
print()
for combo in combos:
    ppcombo(combo)

示例输出：

combos: {(1, 2, 2, 5), (5, 5), (1, 1, 1, 2, 5)}

1*ones + 2*twos + 1*fives
2*fives
3*ones + 1*twos + 1*fives

使用 itertools 将不同代币提名的组合汇总为目标值

Combinations of different coin nominations summed to a target value using itertools

python

collections

combinations

itertools