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.

score 1 · Answer 1 · answered Jan 21 '22 at 23:32

You need to use combinations instead of combinations_with_replacement, so your count checks can be omitted.

Also, why do you check only combinations of length 8? You should check any from 0 to len(all_coins), that's why there should be nested for loop (see more examples of all possible combinations here)

Final code might be:

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)

Thanks, I used 8 for this particular case (3 + 2 +3 = 8 coins in total). I tried with combinations at the beginning, but I did not use the length parameter correctly, now I understand my mistake. — tetris555, Jan 22 '22 at 06:02

martineau · Accepted Answer · 2022-01-22T17:12:51.590

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

Thank you, I did not explain it very well with "no for loop". I meant "no for loop" during generating combinations. — tetris555, Jan 22 '22 at 06:06

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

2 Answers2