Recursive Generator For Change Money - Python

First, thanks for any help. I have this recursive code for counting ways of change from a list of coins and a given amount. I need to write a recursive generator code that presen

Solution 1:

Btw this reminds me of Problem 31.

If you are using Python 3.3+ we can write change_gen with yield from:

defchange_gen(amount, coins):
    if amount == 0:
        yield1elif amount < 0ornot coins:
        yield0else:
        yieldfrom change_gen(amount, coins[:-1])
        yieldfrom change_gen(amount - coins[-1], coins)

or without yield from

defchange_gen(amount, coins):
    if amount == 0:
        yield1elif amount < 0ornot coins:
        yield0else:
        for element in change_gen(amount, coins[:-1]):
            yield element
        for element in change_gen(amount - coins[-1], coins):
            yield element

Tests

import random


for _ in range(10):
    amount = random.randint(0, 900)
    coins = list({random.randint(1, 100)
                  for _ in range(random.randint(1, 10))})
    assertcountChange(amount, coins) == sum(change_gen(amount, coins))

worked fine, so it seems to give similar output

Note

You should remember that for large values of amount and small coins we may reach recursion limit (max depth is near 1000 on my machines).

---

EDIT

if you want to get which coins were used we can add extra parameter for them

defchange_gen(amount, left_coins, used_coins):
    if amount == 0:
        yield used_coins
    elif amount < 0ornot left_coins:
        yieldelse:
        yieldfrom change_gen(amount, left_coins[:-1],
                              used_coins=used_coins[:])
        yieldfrom change_gen(amount - left_coins[-1],
                              left_coins,
                              used_coins[:] + [left_coins[-1]])

possible problem here is that in situations when amount is negative or no coins left None object will be yielded, but it's ok, we can filter them from results using filter:

for e infilter(None, change_gen(5, [1, 2, 3], used_coins=[])):
    print(e)

gives us

[1, 1, 1, 1, 1]
[2, 1, 1, 1]
[2, 2, 1]
[3, 1, 1]
[3, 2]

Solution 2:

this is the pattern. i asked to complete it