#!/usr/bin/env python3
# Copyright and related rights waived under CC0
# ()
'''
Verifying currency orderliness for change-making
The "change-making problem" asks us to find the optimal way to make change
using a some currency, i.e. the way that uses the fewest coins to represent
a given value. A currency is "orderly" (a.k.a. "canonical", "standard", or
"greedy") if a greedy algorithm can be relied upon to make optimal change.
This module can check a currency for orderliness and make optimal change
with orderly currencies. There are two key data structures expected by
these functions:
currency:
The set of denominations ("coin values") that make up the currency. Every
currency must contains a ones (1) denomination.
Must be a list of positive integers, sorted in descending order (with 1 as
the last element), with no duplicates.
coinrep:
A multiset of coins from a currency, together representing some value.
Associates each denomination with a non-negative integer denoting the
number of coins (possibly zero) of that denomination that are used.
Represented as a list of 2-tuples consisting of a denomination followed by
the count. The list must be sorted in descending order of denomination,
with exactly one entry for each of the original currency's denominations.
Unused denominations are represented with a count of zero.
Bibliography:
D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem.
Operations Reseach Letters, 33(3):231-234, 2005.
A. & M. Adamaszek. Combinatorics of the change-making problem.
European Journal of Combinatorics, 31:47-63, 2010.
cs.stackexchange: "When can a greedy algorithm solve the coin change problem?"
'''
from itertools import combinations_with_replacement
def coinrep_value(coinrep):
'''Get the total value of the coins in coinrep.'''
return sum(denom * count for (denom, count) in coinrep)
def coinrep_count(coinrep):
'''Get the number of coins in coinrep.'''
return sum(count for (denom, count) in coinrep)
def grdy_coinrep(value, currency):
'''
Represent a value using coins in a currency.
Uses the greedy algorithm to produce a coinrep representing the given
value using the denominations in given currency. If the currency is
orderly, then this coinrep is guaranteed to optimal (i.e. use the
minimum number of coins necessary).
Use is_orderly() or orderly_conterex() to determine if a currency is
orderly.
'''
coinrep = []
remaining = value
for denom in currency:
count, remaining = divmod(remaining, denom)
coinrep.append((denom, count))
return coinrep
def orderly_counterex(currency):
'''
Determine if a currency is orderly, give a counterexample if not.
If the currency is not orderly, this function returns a counterexample
to prove it: it identifies a value for which grdy_coinrep() does not
produce an optimal representation (uses more coins than needed) and
returns a coinrep that represents that value with fewer coins.
If the currency is orderly, then return None.
Implements the algorithm from:
D. Pearson. A Polynomial-time Algorithm for the Change-Making
Problem. Operations Reseach Letters, 33(3):231-234, 2005.
'''
def mk_candidate(i, j):
candidate = []
template = grdy_coinrep(currency[i - 1] - 1, currency)
for denom, count in template[:j]:
candidate.append((denom, count))
denom, count = template[j]
candidate.append((denom, count + 1))
for denom, count in template[j+1:]:
candidate.append((denom, 0))
return candidate
def is_counterexample(candidate):
value = coinrep_value(candidate)
ref = grdy_coinrep(value, currency)
return coinrep_count(candidate) < coinrep_count(ref)
n = len(currency)
for i, j in combinations_with_replacement(range(1, n), 2):
candidate = mk_candidate(i, j)
if is_counterexample(candidate):
return candidate
return None
def is_orderly(currency):
'''
Determines if a currency is orderly.
See orderly_counterex()
'''
return orderly_counterex(currency) is None
if __name__ == '__main__':
import sys
currency = sorted(set(int(arg) for arg in sys.arg), reverse=True)
counterex = orderly_counterex(currency)
if currency is None:
print('Currency is orderly.')
else:
value = conrep_value(counterex)
ref = grdy_coinrep(value, currency)
print('Currency is not orderly.')