Change-making and currency orderliness

Posted on April 20, 2015

The “change-making problem” asks us to find the optimal way to make change using a some currency, i.e. a way that uses the fewest coins possible 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.

Anyone who is building a change-maker for a specific currency may want to test that currently for orderliness. Change-making is NP-hard when we include support for the non-orderly currencies, and since most real-world currencies are orderly, that complexity is usually unnecessary.

Testing for orderliness is non-trivial, however, and it benefits from computer assistance. As of 2015, the best we have is an O(n³) algorithm due to David Pearson. This python module is a quick-and-dirty implementation of that algorithm.

More info (including citations) are included in the module docstring.

Example usage:

Is US coinage orderly?

$ python3 Python 3.4.0 (default, Apr 11 2014, 13:05:11) [GCC 4.8.2] on linux Type "help", "copyright", "credits" or "license" for more information. >>> from orderlycur import * >>> us_coins = [100, 50, 25, 10, 5, 1] >>> is_orderly(us_coins) True

Yes, it is. What about common UK coinage?

>>> uk_coins = [200, 100, 50, 20, 10, 5, 2, 1] >>> is_orderly(uk_coins) True

That currency is orderly too. But what happens when we add the 25p commemorative coin?

>>> uk_coins.insert(3, 25)
>>> uk_coins [200, 100, 50, 25, 20, 10, 5, 2, 1] >>> is_orderly(uk_coins) False

Introducing the 25p coin has killed orderliness. If we like, we can look at the counterexample that Pearson’s algorithm gives us.

>>> counterexample = orderly_counterex(uk_coins) >>> counterexample [(200, 0), (100, 0), (50, 0), (25, 0), (20, 2), (10, 0), (5, 0), (2, 0), (1, 0)] >>> coinrep_value(counterexample) 40 >>> coinrep_count(counterexample) 2 >>> ref = grdy_coinrep(40, uk_coins) >>> ref [(200, 0), (100, 0), (50, 0), (25, 1), (20, 0), (10, 1), (5, 1), (2, 0), (1, 0)] >>> coinrep_value(ref) 40 >>> coinrep_count(ref) 3 >>>

The counterexample shows that 40p is optimally represented with 2 coins (2 20p coins, specifically), but the greedy algorithm (grdy_coinrep()) wants to use 3 coins (a 25p, a 10p, and a 5p). The greedy algorithm cannot be trusted to make optimal change here.

Licence

To the extent possible under law, Daniel Gnoutcheff has waived all copyright and related or neighboring rights to orderlycur. This work is published from: United States.