
November 8th, 2015, 12:28 PM
#1
How to keep list local to the function call (Recursion) in Python
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
Code:
# 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))

November 8th, 2015, 02:32 PM
#2
Re: How to keep list local to the function call (Recursion) in Python
At the start of the function, make a copy:
Code:
check = list(check)
To avoid confusion, I would remove the global variable named check and write:
Code:
Coin_Change_Count(N, [0, 0, 0, 0])

November 8th, 2015, 09:11 PM
#3
Re: How to keep list local to the function call (Recursion) in Python
Originally Posted by laserlight
At the start of the function, make a copy:
Code:
check = list(check)
To avoid confusion, I would remove the global variable named check and write:
Code:
Coin_Change_Count(N, [0, 0, 0, 0])
I made the following changes as you said but still I'm not getting expected result.
Code:
# 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))

November 8th, 2015, 10:41 PM
#4
Re: How to keep list local to the function call (Recursion) in Python
Originally Posted by atinesh229
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:
Code:
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:
Code:
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:
Code:
coin_change_count(N)
Originally Posted by atinesh229
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?
Last edited by laserlight; November 8th, 2015 at 10:44 PM.

November 8th, 2015, 10:43 PM
#5
Re: How to keep list local to the function call (Recursion) in Python
Originally Posted by laserlight
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:
Code:
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:
Code:
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
Code:
check = list(check)
at start of the function, But still didn't worked. Here is the expected Output.
Code:
>> [[2, 0, 0, 1], [0, 0, 2, 0], [1, 1, 1, 0], [2, 2, 0, 0], [4, 0, 0, 0]]
5
Last edited by atinesh229; November 8th, 2015 at 10:46 PM.

November 9th, 2015, 03:29 AM
#6
Re: How to keep list local to the function call (Recursion) in Python
Originally Posted by atinesh229
Here is the expected Output.
Code:
>> [[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 reread the instructions that you posted in post #1, and it seems that the expected output should be:
Code:
[[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:
Code:
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.
Last edited by laserlight; November 9th, 2015 at 03:51 AM.
Tags for this Thread
Posting Permissions
 You may not post new threads
 You may not post replies
 You may not post attachments
 You may not edit your posts

Forum Rules

Click Here to Expand Forum to Full Width
