How to keep list local to the function call (Recursion) in Python

[atinesh229]

I'm trying to implement Coin Changing Problem which states that

Coin Changing problem is described as given a value N, if we want to make change for N cents, and we have infinite supply of each of S = {S1, S2, . . . , Sm} valued coins, how many ways can we make the change? The order of coins doesn’t matter. Identify all possible ways of changing N cent by Greedy Method. For example, for N = 4 and S = {1, 2, 3}, there are four solutions: {1, 1, 1, 1}, {1, 1, 2}, {2, 2}, {1, 3}. So output should be 4. For N = 10 and S = {2, 5, 3, 6}, there are five solutions: {2, 2, 2, 2, 2}, {2, 2, 3, 3}, {2, 2, 6}, {2, 3, 5}and{5, 5}. So the output should be 5.

In my below python implementation I'm using a list name check. Problem is that the program is using same check list throughout its run time and hence I'm getting wromg result. It should use the check list which local to its function call. Can anybody find a way out of this

# N
N = 10

# Set of Changes
s = [2, 3, 5, 6]

lst = []
check = [0, 0, 0, 0]

def Coin_Change_Count(C, check):       
    for k in range(len(s)):        
        i = len(s) - k - 1
        t = C - s[i]
        
        if (t >= 0):
            if (s[i] == 2):
                check[0] += 1
            elif (s[i] == 3):
                check[1] += 1
            elif (s[i] == 5):
                check[2] += 1
            elif (s[i] == 6):
                check[3] += 1
            
            if (t >= s[0]):
                Coin_Change_Count(t, check)
            
            if (t == 0):
                if (not (check in lst)):
                    lst.append(check)
                    
Coin_Change_Count(N, check)
print(len(lst))

[laserlight]

At the start of the function, make a copy:

check = list(check)

To avoid confusion, I would remove the global variable named check and write:

Coin_Change_Count(N, [0, 0, 0, 0])

[atinesh229]

At the start of the function, make a copy:

check = list(check)

To avoid confusion, I would remove the global variable named check and write:

Coin_Change_Count(N, [0, 0, 0, 0])

I made the following changes as you said but still I'm not getting expected result.

# N
N = 10

# Set of Changes
s = [2, 3, 5, 6]

lst = []

def coin_change_count(C, check):
    # if not empty list, setup a new check list local to function
    if not check:
        check = [0, 0, 0, 0]
        
    for k in range(len(s)):
        if (C == N):
            check = [0, 0, 0, 0]
        i = len(s) - k - 1
        t = C - s[i]
        
        if (t >= 0):
            if (s[i] == 2):
                check[0] += 1
            elif (s[i] == 3):
                check[1] += 1
            elif (s[i] == 5):
                check[2] += 1
            elif (s[i] == 6):
                check[3] += 1
                    
            if (t >= s[0]):
                coin_change_count(t, check)
            
            if (t == 0):
                if (not (check in lst)):
                    lst.append(check)
                    
coin_change_count(N, [0, 0, 0, 0])
print(lst)
print(len(lst))

[laserlight]

I made the following changes as you said

I don't see a list(check) in your code, or any other way that you are making a copy of the list.

What I do see is you adding a check for an empty list, but if you want to do that, I suggest:

def coin_change_count(C, check=None):
    # if not empty list, setup a new check list local to function
    if check is None:
        check = [0, 0, 0, 0]
    # ...

Get rid of this:

if (C == N):
    check = [0, 0, 0, 0]

Actually, I would rename C to something more descriptive, and in lower case since it is not a file scope constant.

Finally, to call it:

coin_change_count(N)

but still I'm not getting expected result.

I can see that the test input is hard coded, I can run the program to obtain the actual output, but what is the expected output?

[atinesh229]

I don't see a list(check) in your code, or any other way that you are making a copy of the list.

What I do see is you adding a check for an empty list, but if you want to do that, I suggest:

def coin_change_count(C, check=None):
    # if not empty list, setup a new check list local to function
    if check is None:
        check = [0, 0, 0, 0]
    # ...

then to call it:

coin_change_count(N)

I can see that the test input is hard coded, I can run the program to obtain the actual output, but what is the expected output?

I tried putting

check = list(check)

at start of the function, But still didn't worked. Here is the expected Output.

>> [[2, 0, 0, 1], [0, 0, 2, 0], [1, 1, 1, 0], [2, 2, 0, 0], [4, 0, 0, 0]]
5

[laserlight]

Here is the expected Output.

>> [[2, 0, 0, 1], [0, 0, 2, 0], [1, 1, 1, 0], [2, 2, 0, 0], [4, 0, 0, 0]]
5

Hmm... I went to re-read the instructions that you posted in post #1, and it seems that the expected output should be:

[[2, 2, 2, 2, 2], [2, 2, 3, 3], [2, 2, 6], [2, 3, 5], [5, 5]]
5

or with the list elements in some other ordering. This differs from what you stated to be the expected output.

I am a little puzzled by the instruction to use the "Greedy Method" since the usual solution for this with an greedy algorithm has to do with the problem being to find the smallest number of coins needed. If you are going to enumerate all possible ways, then I do not see how this is applicable.

Looking more closely at your code, I think the problem lies more with your algorithm or implementation thereof. Here is my attempt which works for both the examples provided by the instructions, with a small but critical snippet removed so you can try your hand at it:

CENTS_AMOUNT = 10

DENOMINATIONS = sorted([2, 3, 5, 6], reverse=True)


def enumerate_coin_changes(cents_amount, denominations):
    """
    Returns a unique list of lists of possible coin changes for the given
    amount of money in cents.

    cents_amount: integer value for the amount of money in cents
    denominations: list of integers representing coin denominations, sorted in
                   descending order of value
    """

    # Find the next largest denomination that can be part of the change:
    index = next((i for (i, denomination) in enumerate(denominations)
                  if denomination <= cents_amount),
                 len(denominations))
    denominations = denominations[index:]

    if not denominations:
        return []

    coin_changes = []

    current_coin_change = [denominations[0]]
    current_sum = denominations[0]
    while current_sum < cents_amount:
        # Compute the coin changes with smaller denominations for
        # (cents_amount - current_sum), then combine them with the current coin
        # change:
        # ... <your code here> ...

        current_coin_change.append(denominations[0])
        current_sum += denominations[0]

    # Check if the change can consist entirely of multiples of the current
    # denomination:
    if current_sum == cents_amount:
        coin_changes.append(current_coin_change)

    # Account for change consisting entirely of the smaller denominations:
    coin_changes += enumerate_coin_changes(cents_amount, denominations[1:])

    return coin_changes

if __name__ == '__main__':
    coin_changes = enumerate_coin_changes(CENTS_AMOUNT, DENOMINATIONS)
    coin_changes.sort()
    print(coin_changes)
    print(len(coin_changes))

It turned out that I did not need the list(check) trick at all: as you can see, I simply set coin_changes = [] and current_coin_change = [denominations[0]] before going into the loop with recursive calls (i.e., the portion that I removed).

Perhaps one key thing to observe is that I basically avoided global variables altogether. This makes it easier to reason about your program, especially when recursion is involved. It allowed me to think: "returns a unique list of lists of possible coin changes for the current cents amount, so I can recursively call it with a smaller cents amount, then combine what was returned to make up the current cents amount".

Oh, and notice that my code uses descriptive variable names, plus I comment what the function does and what are its parameters for, and where I think the code might need some explanation, I provided appropriate comments.