Question

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.

counting.txt contains some skeleton code. Download it and rename it counting.py. 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)

Answer 1

The subject of this question is Python programming and specifically the implementation of counting algorithms. The question asks for two functions to be implemented: partitions(n,k) that counts how many ways n distinct elements can be grouped into k partitions, and mkCh(a,c) that counts how many ways amount a can be paid with coins {1,5,10,25}.

Step-by-step explanation:

The subject of this question is Python programming and specifically the implementation of counting algorithms. The question asks for two functions to be implemented: partitions(n,k) that counts how many ways n distinct elements can be grouped into k partitions, and mkCh(a,c) that counts how many ways amount a can be paid with coins {1,5,10,25}. The provided code contains skeleton code for the functions.

The partitions function recursively calculates the number of ways k partitions can be formed out of n distinct elements by either grouping an element with the rest or forming its own partition.

The mkCh function calculates the number of ways to pay amount a with coins {1,5,10,25} by considering each coin value.

The assignment is based on concepts discussed in a lecture about counting.

The task requires understanding of combinatorics, a field of mathematics, within computer science principles to implement the functions correctly. An example provided in the assignment indicates that for n=3 and k=2, the 'partitions' function should return 3, and for amount a=32 using coins of denominations 1, 5, 10, and 25, the 'mkCh' function should return 18.