#!/usr/bin/python
#+
# This script computes the number of different ways that combinations
# of a given set of coin denominations can add up to a specified amount.
#
# Call this script as follows:
#
# make_change --coins=denomination,denomination... [--total] amount ...
#
# where amount is one or more amounts (in integer cents) to compute change
# for, denomination is the list of available coin denominations, and
# --total means to only list the total number of ways to make change,
# not show the details of the combinations themselves.
#
# The details of the combinations are displayed on standard output as
# follows:
#
# amount => [n1 * denom1, n2 * denom2 ... ]
#
# where the n are the integer numbers of each coin, and the denom are
# the corresponding coin denomination, to make the total add up to amount.
#-
import sys
import getopt
def CoinsCombination(Coins, Amount) :
"""generator function which yields all possible combinations of
Coins adding up to Amount. Assumes Coins is sorted by increasing
value."""
if len(Coins) == 0 :
if Amount == 0 :
yield ()
else :
return
#end if
else :
Coeff = 0
while True :
for Combi in CoinsCombination(Coins[1:], Amount) :
yield (Coeff,) + Combi
#end for
if Coins[0] > Amount :
break
Coeff += 1
Amount -= Coins[0]
#end while
#end if
#end CoinsCombination
(Opts, Args) = getopt.getopt \
(
sys.argv[1:],
"",
["coins=", "total"]
)
Coins = None
TotalOnly = False
for Keyword, Value in Opts :
if Keyword == "--coins" :
Coins = []
for Denom in Value.split(",") :
Coin = int(Denom)
if Coin <= 0 :
raise getopt.error("bad --coins denomination \"%s\"" % Denom)
#end if
Coins.append(Coin)
#end for
if len(Coins) == 0 :
raise getopt.error("empty --coins specification")
#end if
Coins.sort()
elif Keyword == "--total" :
TotalOnly = True
#end if
#end for
if Coins == None :
raise getopt.error("missing --coins specification")
#end if
if len(Args) == 0 :
raise getopt.error("missing amounts")
#end if
for Amount in Args :
Amount = int(Amount)
NrWays = 0
for Combi in CoinsCombination(Coins, Amount) :
NrWays += 1
if not TotalOnly :
print "%u => [%s]" % \
(Amount,
", ".join(str(a) + " * " + str(b) for a, b in zip(Combi, Coins)))
#end if
#end for
print "%u nr ways = %u" % (Amount, NrWays)
#end for
#//python/4606