# Change-making and currency orderliness

orderlycur.py (python3)

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^{3}) 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.