#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    15
    Rep Power
    0

    Help with python recursion


    hello everyone,
    I tried to create a program which received a number (n) and a list of coins.
    the program needs to find all the possibilities of creating with the list of coins content in order to find the number n.

    example:
    lets say I got n=10.
    and I have a list of [5,10]
    the program should give me all the possibilities which are: [5,5] and [10].
    note ( I must use only recursion, no"while" or something to replace it )
    now I created a code, but frankly , I am lost in my own code.
    I got this program to assist me find all the possibilities
    Code:
    def permuste(elements):
        if len(elements)==0:
            return[[]]
        permutation=[]
        for curr in elements:
            elements_minus_curr=elements[:]
            elements_minus_curr.remove(curr)
            sub_perms=permuste(elements_minus_curr)
            for perm in sub_perms:
                perm.append(curr)
            permutation.extend(sub_perms)
        return permutation
    elements=[1,2,3]
    d=permuste(elements)
    print d
    so I tried to follow this form of program into my program,
    and ended up with this:
    Code:
    def find_changes(n, coins):  
        
        if n < 0:  
            return []  
        if n == 0:  
            return [[]]  
        
        all_changes = []  
           
        for last_used_coin in coins:  
            if n==sum(coins):  
                all_changes.extend(coins)  
            all_used_but_one=coins[:]                      
            all_used_but_one.remove(last_used_coin)  
            new_group_of_coins= find_changes(n,all_used_but_one)  
                          
             
            if n==sum(find_changes(n,all_used_but_one)):  
                for new in new_group_of_coins: 
                    str(last_used_coin)
                    str(new)
                    new.append(last_used_coin) 
                      
            all_changes.extend(new_group_of_coins) 
             
                
                
        return all_changes  
    n=2  
    coins=[1,2]  
    d=find_changes(n, coins)  
    print d
    now, in my code I get a lot of errors such as "'int' object has no attribute 'append'"
    I tried to fix it, but it only led to more errors.

    I ask of you please, tell me if my code is something near to what I desire of it to be, if it is, could you please tell me how can I fix all of those errors?
    if it is not even near to what is desire of it , could you tell me how I should build this program?
    I thank you vary much for reading this far, and hope you could help me somehow.
    I thank you all, and good day.
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    475
    Rep Power
    33
    Some logic is the place to start. The function receives a list [1, 5, 10] and wants to find all coins that will add up to ten. Take the first element and divide 10 by it and see if it is evenly divisable. Slice the first element off the list and do a recursive call to the function to repeat with the next element. Add some print statements while testing to see if the logic is working correctly, and too see what is returned by the function, and you should be good to go. So, for starters, create a function that works correctly for one value in the list and then add in the recursion.
    Last edited by dwblas; November 9th, 2013 at 12:05 PM.
  4. #3
  5. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    logic is a good idea, "evenly divisible" isn't particularly useful. Let's try this:
    Code:
    def change(total, denominations, current, result):
        '''
            doctest.  Run doctest with command 
            $ python -m doctest thisfile.py
    
            >>> result = []
            >>> change(total = 10, denominations = [5, 10], current = [], result = result)
            >>> assert len(result) == 2
            >>> assert [5, 5] in result
            >>> assert [10] in result
        '''
    
        # recursion rule:  find a way to stop the recursion
        s = sum(current)
        if s == total:                        # if the sum is correct, append the result
            result.append(current)
        if total <= s:                        # if the sum is correct or too large, return.
            return
    
        # recursively try all the possibilities
        for denomination in denominations:
            change(total, denominations, current+[denomination], result)
    Simple, and it passes the test, but I think it's wrong. Example:
    Code:
    >>> result = []
    >>> change(10, [1, 5, 10], [], result)
    >>> print(result)
    [[1, 1, 1, 1, 1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 1, 5], [1, 1, 1, 1, 5, 1], [1, 1, 1, 5, 1, 1], [1, 1, 5, 1, 1, 1], [1, 5, 1, 1, 1, 1], [5, 1, 1, 1, 1, 1], [5, 5], [10]]
    Change does not depend on order. The algorotithm could additionally post process the output by sorting each of the lists then retain only the unique entries.

    Or we could not create the entries in the first place. This version of the algorithm works from biggest to smallest thereby avoiding the problem.
    Code:
    def change(total, denominations, current, result):
        '''
            doctest.  Run doctest with command 
            $ python -m doctest thisfile.py
    
            >>> result = []
            >>> change(total = 10, denominations = [5, 10], current = [], result = result)
            >>> assert len(result) == 2
            >>> assert [5, 5] in result
            >>> assert [10] in result
        '''
        # recursion rule:  find a way to stop the recursion
        s = sum(current)
        if s == total:                        # if the sum is correct, append the result
            result.append(current)
        if total <= s:                        # if the sum is correct or too large, return.
            return
    
        denominations.sort(reverse = True)  # use a sorting step
        # recursively try all the possibilities
        for (i, denomination,) in enumerate(denominations):
            change(total, denominations[i:], current+[denomination], result)
    [code]Code tags[/code] are essential for python code and Makefiles!
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Nov 2013
    Posts
    15
    Rep Power
    0
    thank you for your answers, they were insightful.
    I found out there is a simple solution to my problem.
    :
    Code:
     
    
    
    def find_changes(n, coins):
        
        if n < 0:
            return []
        if n == 0:
            return [[]]
    
        all_changes = []
    
        for last_used_coin in coins:
          
            new_coins=coins[:]
            new_coins.remove(last_used_coin)
           
            t=find_changes(n-last_used_coin,coins)
            for coin in t:
                coin.append(last_used_coin)
            all_changes.extend(t)   
    
        return all_changes
    
    
    
    
    
    n=10
    coins=[1,2,5]
    d=find_changes(n, coins)
    print d
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    May 2009
    Posts
    475
    Rep Power
    33
    I did not find the single [10] entry when running this code. Take a look at the "coins" list if you want to include it.
    the program should give me all the possibilities which are: [5,5] and [10].
    Last edited by dwblas; November 10th, 2013 at 04:43 PM.
  10. #6
  11. Contributing User
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Aug 2011
    Posts
    4,837
    Rep Power
    480
    The useless statements

    new_coins=coins[:]
    new_coins.remove(last_used_coin)

    have no benefit.

    And, like my first attempt, your program answers with
    [2, 1, 1, 1, 1, 1, 1, 1, 1], [1, 2, 1, 1, 1, 1, 1, 1, 1]
    as distinct.
    [code]Code tags[/code] are essential for python code and Makefiles!

IMN logo majestic logo threadwatch logo seochat tools logo