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

Question

If I have 3 types of coins (one, two, and five). I have different amounts of each coin. How can I get all combinations equal to a certain target?

For example:

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

Using this code:

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")

Gave these combinations with sum of target:

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

However, I don't feel this is the best approach, how can this be solved in a more elegant way? The question is for using itertools, collections, or other modules to simplify that task.

No nested for loops.

Answer 1

You can use a list comprehension to kind of hide the fact, by you really do need to use nested for loops to solve this in a general way (to avoid potentially having to hardcode a very large number non-nested ones):

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)

You could print the results in a more readable way by adding a helper function:

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)

Sample output:

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