CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 6 of 6
  1. #1
    Join Date
    Nov 2015
    Posts
    6

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

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

    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])
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Nov 2015
    Posts
    6

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

    Quote Originally Posted by laserlight View Post
    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))

  4. #4
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

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

    Quote 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)
    Quote 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  5. #5
    Join Date
    Nov 2015
    Posts
    6

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

    Quote Originally Posted by laserlight View Post
    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.

  6. #6
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,765

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

    Quote 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 re-read 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.
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

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
  •  





Click Here to Expand Forum to Full Width

Featured