Python Forum
Print the frequency of each coin for the combinations that sum to the amount N
Thread Rating:
  • 1 Vote(s) - 1 Average
  • 1
  • 2
  • 3
  • 4
  • 5
Print the frequency of each coin for the combinations that sum to the amount N
#1
Description:

The different combinations of the coins in the range of 1 to N that sum to the amount N needs to be printed. I have used recursive function for printing the different coin combinations.

n=4
The above variable is the amount.
arr=[1,2,3,4]
Above array contains the list of coins.

I am getting all the lines for the output but not in the same order.
In the problem its mandatory that the output should be printed in exactly the same order.
Please help me out in printing the combinations in exactly the same order.

OUTPUT OBTAINED:


Output:
|| Coin 1 occurs: 4 times || Coin 2 occurs: 0 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times || Coin 1 occurs: 2 times || Coin 2 occurs: 1 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times || Coin 1 occurs: 1 times || Coin 2 occurs: 0 times || Coin 4 occurs: 0 times || Coin 3 occurs: 1 times || Coin 1 occurs: 0 times || Coin 2 occurs: 2 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times || Coin 1 occurs: 0 times || Coin 2 occurs: 0 times || Coin 4 occurs: 1 times || Coin 3 occurs: 0 times Total combinations is 5
DESIRED OUTPUT:

Output:
|| Coin 1 occurs: 0 times || Coin 2 occurs: 0 times || Coin 4 occurs: 1 times || Coin 3 occurs: 0 times || Coin 1 occurs: 0 times || Coin 2 occurs: 2 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times || Coin 1 occurs: 1 times || Coin 2 occurs: 0 times || Coin 4 occurs: 0 times || Coin 3 occurs: 1 times || Coin 1 occurs: 2 times || Coin 2 occurs: 1 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times || Coin 1 occurs: 4 times || Coin 2 occurs: 0 times || Coin 4 occurs: 0 times || Coin 3 occurs: 0 times Total combinations is 5
n=4
arr=[1,2,4,3]

"""Function to calculate the number of different combinations"""
def changes(amount,c):
    ways=[0]*(amount+1)
    ways[0]=1
    for x in c:
        for y in range(x,amount+1):
            ways[y]+=ways[y-x]
    return ways[amount]

"""Recursive function that prints the combinations"""
def allComb(n,s,start):
    c1=c2=c3=c4=0
    
    if (n==0):
        for z in range(len(s)):

            if (s[z]=="4"):
                c4+=1    
            elif(s[z]=="3"):
                c3+=1       
            elif (s[z]=="2"):
                c2+=1                
            elif(s[z]=="1"):
                c1+=1
 
        print ("|| Coin 1 occurs: %d times"%c1,end=" ")
        print ("|| Coin 2 occurs: %d times"%c2,end=" ")  
        print ("|| Coin 4 occurs: %d times"%c4,end=" ")  
        print ("|| Coin 3 occurs: %d times"%c3,end=" ")    
    
        print("")
    
    for i in  range(start,n+1):
        allComb(n-i,s+str(i)+"",i)                          #Recursion 
    

new_str=""    
allComb(n,new_str,1)                                        #Arguments are given for the Recursion function

z=changes(n,arr)
print("Total combinations is %d "%z)
Reply
#2
Comparing Output with Desired, it appears they are in the same order, but reversed. Since you are using recursion, you can't just reverse a loop.
Suggest you have your recursive function return the string to be printed as a list element rather than actually print. Add the list to the arguments as well, and each time rather than print you append. Then, when allComb finally ends you can print the list in any order.

Generally good practice not to have the output inside the same function that is doing the calculations. Can get you into problems like this.
Reply
#3
Thanks for your help. I am able to get the desired output now.


The below code was used

n=4
arr=[1,2,4,3]
arr1=[]



"""Function to calculate the number of different combinations"""
def changes(amount,c):
    ways=[0]*(amount+1)
    ways[0]=1
    for x in c:
        for y in range(x,amount+1):
            ways[y]+=ways[y-x]
    return ways[amount]

"""Function for appending data to an array"""

def Creat(a,string):
    a.append(string)
    return a


"""Recursive function that prints the combinations"""
def allComb(n,s,start):
    
    
    if (n==0):
        Creat(arr1,s)


     
    for i in  range(start,n+1):
        allComb(n-i,s+str(i)+"",i)                          #Recursion 
     
    return arr1
    
new_str=""    
z=allComb(n,new_str,1)                                        #Arguments are given for the Recursion function


for i in range(len(z)-1,-1,-1):
    c1=c2=c3=c4=0
    for j in z[i]:
        if str(j)=="1":
            c1+=1
        elif str(j)=="2":
            c2+=1
        
        elif str(j)=="3":
            c3+=1
        elif str(j)=="4":
            c4+=1
    print("coin 1 occurs: %d times"%c1,end="||")            
    print("coin 2 occurs: %d times"%c2,end="||") 
    print("coin 4 occurs %d times"%c4,end="||")  
    print("coin 3 occurs %d times"%c3,end="||")          
    
    print("")

result=changes(n,arr)
print("Total combinations is %d "%result)   
The output obtained is

Output:
coin 1 occurs: 0 times||coin 2 occurs: 0 times||coin 4 occurs 1 times||coin 3 occurs 0 times|| coin 1 occurs: 0 times||coin 2 occurs: 2 times||coin 4 occurs 0 times||coin 3 occurs 0 times|| coin 1 occurs: 1 times||coin 2 occurs: 0 times||coin 4 occurs 0 times||coin 3 occurs 1 times|| coin 1 occurs: 2 times||coin 2 occurs: 1 times||coin 4 occurs 0 times||coin 3 occurs 0 times|| coin 1 occurs: 4 times||coin 2 occurs: 0 times||coin 4 occurs 0 times||coin 3 occurs 0 times|| Total combinations is 5
Reply
#4
Please suggest if the above problem can be solved using iteration as well.
If possible then please let me know the logic that can be applied.
Reply


Possibly Related Threads…
Thread Author Replies Views Last Post
  Get 5 most unique combinations of elements in a 2D list wanttolearn 1 2,280 Sep-24-2020, 02:26 PM
Last Post: buran
  Unexpected change to a list in a small amount of self-contained code Johno 5 2,789 Mar-15-2020, 05:06 PM
Last Post: jefsummers
  Random module, coin flipping gus17 3 4,738 Jan-06-2020, 10:29 AM
Last Post: perfringo
  Need help with coin change program Gateux 2 5,960 Jun-25-2019, 02:32 PM
Last Post: perfringo
  Combinations mnnewick 1 2,572 Dec-17-2018, 02:35 PM
Last Post: ichabod801
  Program that displays the number with the greatest amount of factors ilusmd 3 2,773 Nov-01-2018, 08:28 PM
Last Post: ichabod801
  Adding and Removing coins to match Coin Bag Total infinite times Strayfe 8 4,528 Sep-11-2018, 07:30 PM
Last Post: gruntfutuk
  Looping over amount of attempts Beatenberg 4 6,158 Oct-17-2017, 07:47 AM
Last Post: Beatenberg
  Four digit combinations EHod 4 7,699 Aug-13-2017, 09:14 PM
Last Post: EHod

Forum Jump:

User Panel Messages

Announcements
Announcement #1 8/1/2020
Announcement #2 8/2/2020
Announcement #3 8/6/2020