How do I recursively increment the first value in a list and append to a nested list in python?

Question

I wrote a function called change which takes in an int and a list of coins.

It recursively checks what the least amount of coins are needed to create that amount and returns this number. Now I am trying to modify this function to take the same input but instead return a list with the number of coins and a list of coins used.

def change(amount, coins):
    if amount == 0:
        return 0
    if coins == []:
        return float("inf")
    if coins[0] > amount:
        return change(amount, coins[1:])
    use_it = 1+change(amount-coins[0], coins)
    lose_it = change(amount, coins[1:])
    return min(use_it, lose_it)

I began modifying this code but I'm not sure how to manipulate the return value given that it's a list:

def giveChange(amount, coins):
    if amount == 0:
        return [0, []]
    if coins == []:
        return [float("inf"), []]
    if coins[0] > amount:
        return giveChange(amount, coins[1:])
    use_it = 1 + giveChange(amount-coins[0], coins)
    lose_it = giveChange(amount, coins[1:])
    listOfCoins = 
    return [min(use_it, lose_it), listOfCoins]

I have this so far but my use_it line is wrong because the function now returns a list. Could I simply do this:

use_it = 1 + giveChange(amount-coins[0], coins)[0]

I am not sure how to build up the list of coins so that I can return it with the amount of coins at the end.

I'm not entirely sure what your programming question is, but perhaps you need to research [unpacking](http://stackoverflow.com/questions/6967632/unpacking-extended-unpacking-and-nested-extended-unpacking). — ChrisP, Feb 17 '16 at 03:13
You may want to update your question title, it doesn't really reflect what you are actually asking. — AChampion, Feb 17 '16 at 04:47

melalonso · Accepted Answer · 2016-02-18T01:56:56.297

return a list with the number of coins and a list of coins used.

I think this is what you are looking for:

def giveChange(amount, coins):
    if amount == 0:
        return [0, []]
    if coins == []:
        return [float("inf"), []]
    if coins[0] > amount:
        return giveChange(amount, coins[1:])
    [use_it_amt, use_it_list] = giveChange(amount-coins[0], coins)
    [lose_it_amt, lose_it_list] = giveChange(amount, coins[1:])
    if use_it_amt+1 < lose_it_amt:
        use_it_list.append(coins[0])
        return [use_it_amt+1, use_it_list]
    else:
        return [lose_it_amt, lose_it_list]

Here you can see it working: https://repl.it/Bn2T

As this is Dynamic Programming something good would be to use a memoization table to prevent the recalculation of sub problems, furthermore it is stack dependent and will give you StackOverflow if the quantity of recursion calls is too large.

Thank you that's exactly what I was looking for! The only issue I found was that `lose_it_list.append(coins[0])` at the end was unnecessary because it was appending coins that were not being used. — Bryan Jiménez, Feb 17 '16 at 20:54

AChampion · Answer 2 · 2016-02-17T04:50:00.450

Just handle the second parameter correctly throughout your code, the only difficult is use_it needs to add 1 to the number of coins and add the coin[0] to the list of coins used. min will need to take in account and key on the first parameter:

def give_change(amount, coins):
    if amount == 0:
        return [0, []]
    if coins == []:
        return [float('inf'), []]
    if coins[0] > amount:
        return give_change(amount, coins[1:])
    use_it = [x+y for x,y in zip(give_change(amount-coins[0], coins), [1,[coins[0]]])]
    lose_it = give_change(amount, coins[1:])
    return min(use_it, lose_it, key=lambda x: x[0])

>>> give_change(53, [1, 2, 5, 10, 25, 50, 100])
[3, [50, 2, 1]]

Taking a more dynamic programming approach to this you can do it without recursion. I've assumed you can reuse the coins (as your original code also reused coins). give_change now returns all the ways you can achieve the amount with the coins, which you can just min with a key=len:

def give_change(amount, coins):
    ways = [list() for _ in range(0, amount+1)]
    ways[0].append([])

    for coin in coins:
        for i, x in enumerate(range(coin, amount+1)):
            ways[x].extend(l+[coin] for l in ways[i])
    return ways[amount]

>>> give_change(3, [1, 2, 5, 10, 25, 50, 100])
[[1, 1, 1], [1, 2]]
>>> min(give_change(3, [1, 2, 5, 10, 25, 50, 100]), key=len)
[1, 2]
>>> min(give_change(53, [1, 2, 5, 10, 25, 50, 100]), key=len)
[1, 2, 50]

How do I recursively increment the first value in a list and append to a nested list in python?

2 Answers2