使用Python中的itertools将不同硬币命名的组合汇总为目标值

tetris555 • 3 年前 • 1416 次点击

如果我有三种硬币(一、二、五)。我有不同数量的硬币。我怎样才能使所有的组合都等于某个目标?

例如:

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 循环。

Python社区是高质量的Python/Django开发社区
本文地址：http://www.python88.com/topic/128952

1416 次点击

文章 [ 2 ] | 最新文章 3 年前

• 1 楼

martineau 3 年前

你可以用 list comprehension 为了掩盖事实,你真的做需要使用嵌套 for 循环以通用方式解决此问题(避免可能需要硬编码很大数量(非嵌套的):

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

• 2 楼

Alex Kosh 3 年前

你需要使用 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)

登录后回复