Implementation of the change making algorithm

I wrote a set of python classes for solving the change making problem, in various forms.


Given the coin denominations and values:

• Find all possible ways of making change.

• Find a best way of making change (minimize number of coins).

• Determine whether it is possible to make change.

This version of the project on github.

Main file: change.py

```
# An implementation solving the change making problem and related problems.
# See http://en.wikipedia.org/wiki/Change-making_problem

from itertools import takewhile

def abstractMethod(): raise NotImplementedError('Abstract method')

class CoinChanger(object):
def __init__(self, denominations):
CoinChanger.verify_denominations(denominations)
self.denominations = tuple(sorted(denominations))
self.cache = dict()

@staticmethod
def verify_denominations(denominations):
assert len(set(denominations)) == len(denominations)
assert all(type(d) == int for d in denominations)
assert all(d > 0 for d in denominations)

def change_for(self, amount):
if amount not in self.cache:
self.cache[amount] = self._value_to_store_for_amount(self._change_for(amount))

for change in self.cache[amount]:
yield change

def _change_for(self, amount):
if amount == 0:
yield self._get_value_for_zero_change()
return

for i, d in self.denominations_less_than_or_equal_to(amount):
remaining_amount = amount - d
for change in self.change_for(remaining_amount):
yield self._get_change_for_denomination(change, d, i)

def denominations_less_than_or_equal_to(self, amount):
'''Yields (index, denomination)'''
return takewhile(lambda (i, d): d <= amount, enumerate(self.denominations))

def _get_value_for_zero_change(self):
abstractMethod()

def _get_change_for_denomination(self, change, denomination, denomination_index):

1. Stop writing classes

The title for this section comes from Jack Diederich's PyCon 2012 talk.

A class represents a group of objects with similar behaviour, and an object represents some kind of persistent thing. So when deciding what classes a program is going to need, the first question to ask is, "what kind of persistent things does this program need to represent?"

In this case the persistent things are:

• collections of denominations of coins (represented by lists of numbers); and

• caches of previously computed results (represented by dictionaries).

There does not seem to be a need for any other class of object.

1. Other review comments

-
If you limited all lines to a maximum of 79 characters, as recommended by the Python style guide (PEP8), we wouldn't have to scroll horizontally to read it here.

-
Trying to run the code in the post, I get IndentationError. Possibly a copy-paste problem?

-
There are docstrings for the classes but they do not explain how to use them. How do I construct instances of these classes? What methods may I call?

-
This assertion is too strong:

assert all(type(d) == int for d in denominations)

The change-making algorithm works with other kinds of numbers than int, for example it works just fine with fractions. See §5 below.

-
There are, in general, a very large number of ways of making change. So in the case of AllPossibilitiesCoinChanger, it's not a good idea to try to return them all as a list: this will soon fill the available memory. A better strategy is to generate the results one by one, to keep the memory usage bounded.

-
For the same reason, it makes no sense to try to cache the results of AllPossibilitiesCoinChanger: this will fill the available memory. Caching these results doesn't even improve the runtime complexity: copying them out of the cache is no faster (asymptotically speaking) than generating them again.

1. Separation of concerns

The logic for maintaining a cache of previously computed results (that is, for memoization) is mixed in with the logic for change-making. It would be better to separate these concerns for clarity, maintainability, and reuse.

Memoization is most elegantly done using a decorator, for example @functools.lru_cache.

1. Revised implementation

Instead of classes, write functions!

from functools import lru_cache

def partitions(n, values):
    """Generate the ways of expressing n as a sum of items from the tuple
    values (with repetition, ignoring order).

    >>> list(partitions(6, (1, 2, 5)))
    [(1, 1, 1, 1, 1, 1), (1, 1, 1, 1, 2), (1, 1, 2, 2), (1, 5), (2, 2, 2)]

    """
    if n == 0:
        yield ()
    elif not values:
        return
    else:
        first = values[0]
        if first >> # Partition numbers: https://oeis.org/A000041
    >>> [count_partitions(i, tuple(range(1, 16))) for i in range(16)]
    [1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176]

    """
    if n == 0:
        return 1
    elif not values:
        return 0
    else:
        first = values[0]
        count = count_partitions(n, values[1:])
        if first >> partitionable(11, (4, 5))
    False
    >>> partitionable(59, (6, 7))
    True

    """
    return any(True for _ in partitions(n, values))

Notes:

-
The docstrings contain doctests, small code examples that double as tests. These are runnable using the doctest module.

-
I've omitted minimum_partitions, but it should be clear from the above how I would write it.

-
The similarities in the code for partitions and count_partitions makes it tempting to try to combine them into a single algorithm. But this is hopeless, because partitions is a generator that is not memoized (as discussed in §2.6 above), whereas count_partitions is an ordinary function that is memoized. Even if we changed partitions to return a list, these functions are so simple that there would be as many differences as there are similarities, so that trying to combine them would just result in a mess that was hard to understand and maintain.

1. Fractions

Here's an example to show why you might not want to insist that the values are ints:

>>> from fractions import Fraction
>>> list(partitions(1, tuple(Fraction(1, i) for i in range(2, 5))))
[(Fraction(1, 2), Fraction(1, 2)),
 (Fraction(1, 2), Fraction(1, 4), Fraction(1, 4)),
 (Fraction(1, 3), Fraction(1, 3), Fraction(1, 3)),
 (Fraction(1, 4), Fraction(1, 4), Fraction(1, 4), Fraction(1, 4))]

StackExchange Code Review Q#91716, answer score: 8