Counting This third python programming assignment, PA3, is about counting. You will write two functions partitions(n, k) that counts in how many ways n distinct elements can be grouped into k (non empty) partitions, and mkCh(a, c) that counts in how many ways amount a can be paid with coins {1,5,10,25}. Both algorithms are discussed in lecture 15: counting. Start with the skeleton code. A correct implementation of counting:
python3 counting. py 3 2
produces
n: 3 k: 2 partitions: 3
amount: 32 coins: [1, 5, 10, 25] ways: 18
counting. txt
import sys
coins = [1,5,10,25]
def partitions(n, k):
"""
pre 00
post return the number of ways k partitions
can be formed out of n distinct elements
"""
# if k==n or k==1 :
# there is only one way to form partitions
# else :
# select an element a, and
# either
# form k partitions with the rest of the elements
# and let a join one of these k groups
# or
# let a form its own partition, and
# form k-1 partitions with the rest
return 1
def mkCh(a, c):
"""
given coin set {1,5,10,25} count how many ways we can pay amount a,
c indicates which coin is considered first. c starts as the index
of the last coin value (len(coins)-1)
"""
return 1
if __name__ == "__main__":
# partititions
d = len(sys. argv)>3
n = int(sys. argv[1])
k = int(sys. argv[2])
p = partitions(n, k)
print("n:",n,"k:",k, "partitions:",p)
# make change
c = len(coins)-1
a = 10*n+k
ways = mkCh(a, c)
print("amount:", a, "coins:", coins, "ways:", ways)