counting.py

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)

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 nkCh (a, c) that counts in how many ways amount a can be paid with coins 11,5,10,251. 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 partitiona: 3 amount: 32 coins: 1, 5, 10, 25) ways: 18 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 nkCh (a, c) that counts in how many ways amount a can be paid with coins 11,5,10,251. 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 partitiona: 3 amount: 32 coins: 1, 5, 10, 25) ways: 18