#!/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