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

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.

CodePudding user response：

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)

CodePudding user response：

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

rom itertools import chain, combinations
from pprint import pprint


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

results = []
for combo in chain.from_iterable(combinations(all_coins, r=length)
                                     for length in range(1, len(all_coins))):
    if sum(combo) == target:
        results.append(combo)

pprint(results)