Implementation of the change making algorithm

Question

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):
 abstractMethod()
 def _value_to_store_for_amount(self, value):
 abstractMethod()
class AllPossibilitiesCoinChanger(CoinChanger):
 '''Given a set of denominations, yields all possible ways of making change for a given value.'''
 def __init__(self, denominations):
 super(AllPossibilitiesCoinChanger, self).__init__(denominations)
 def _get_value_for_zero_change(self):
 return tuple([0] * len(self.denominations))
 def _get_change_for_denomination(self, change, denomination, denomination_index):
 new_change = list(change)
 new_change[denomination_index] += 1
 return tuple(new_change)
 def _value_to_store_for_amount(self, value):
 return list(value)
class MinimumCoinChanger(CoinChanger):
 '''Given a set of denominations, a best way (minimize the number of coins) of making change for a given value.'''
 def __init__(self, denominations):
 super(MinimumCoinChanger, self).__init__(denominations)
 def _get_value_for_zero_change(self):
 return tuple([0] * len(self.denominations))
 def _get_change_for_denomination(self, change, denomination, denomination_index):
 new_change = list(change)
 new_change[denomination_index] += 1
 return tuple(new_change)
 def _value_to_store_for_amount(self, value):
 try:
 return [ min(value, key=sum) ]
 except ValueError:
 return []
class BooleanCoinChanger(CoinChanger):
 '''Given a set of denominations, determines whether it is possible to make change for a given value'''
 def __init__(self, denominations):
 super(BooleanCoinChanger, self).__init__(denominations)
 def _get_value_for_zero_change(self):
 return True
 def _get_change_for_denomination(self, change, denomination, denomination_index):
 assert change == True
 return change
 def _value_to_store_for_amount(self, value):
 for v in value:
 return [ True ]
 else:
 return []

---

Test file: change_test.py

from change import AllPossibilitiesCoinChanger, MinimumCoinChanger, BooleanCoinChanger
import unittest
class AllPossibilitiesCoinChangerTest(unittest.TestCase):
 def test_change_for_zero(self):
 changer = AllPossibilitiesCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 0, (0,0))
 def test_change_for_one(self):
 changer = AllPossibilitiesCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 1, (1,0))
 def test_change_for_multiple(self):
 changer = AllPossibilitiesCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 3, (3,0), (0,1))
 def test_change_for_many(self):
 changer = AllPossibilitiesCoinChanger((1,3,4))
 self.assertChangeForAmountIs(changer, 6, (6,0,0), (3,1,0), (2,0,1), (0,2,0))
 def test_impossible_change(self):
 changer = AllPossibilitiesCoinChanger((3,5))
 self.assertChangeForAmountIs(changer, 4)
 self.assertChangeForAmountIs(changer, 2)
 def assertChangeForAmountIs(self, changer, amount, *values):
 actual_values = set(changer.change_for(amount))
 unordered_values = set(values)
 self.assertEquals(unordered_values, actual_values)
 self.assertEquals(len(values), len(unordered_values))
class MinimumCoinChangerTest(unittest.TestCase):
 def test_change_for_zero(self):
 changer = MinimumCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 0, (0,0))
 def test_change_for_one(self):
 changer = MinimumCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 1, (1,0))
 def test_change_for_multiple(self):
 changer = MinimumCoinChanger((1,3))
 self.assertChangeForAmountIs(changer, 3, (0,1))
 def test_change_for_many(self):
 changer = MinimumCoinChanger((1,3,4))
 self.assertChangeForAmountIs(changer, 6, (0,2,0))
 def test_impossible_change(self):
 changer = MinimumCoinChanger((3,5))
 self.assertNotChangeable(changer, 4)
 self.assertNotChangeable(changer, 2)
 def assertChangeForAmountIs(self, changer, amount, change):
 actual_change = list(changer.change_for(amount))
 self.assertEquals([change], actual_change)
 def assertNotChangeable(self, changer, amount):
 self.assertEquals([], list(changer.change_for(amount)))
class BooleanCoinChangerTest(unittest.TestCase):
 def test_change_for_zero(self):
 changer = BooleanCoinChanger((1,3))
 self.assertChangeable(changer, 0)
 def test_change_for_one(self):
 changer = BooleanCoinChanger((1,3))
 self.assertChangeable(changer, 1)
 def test_change_for_multiple(self):
 changer = BooleanCoinChanger((1,3))
 self.assertChangeable(changer, 3)
 def test_change_for_many(self):
 changer = BooleanCoinChanger((1,3,4))
 self.assertChangeable(changer, 6)
 def test_impossible_change(self):
 changer = BooleanCoinChanger((3,5))
 self.assertNotChangeable(changer, 4)
 self.assertNotChangeable(changer, 2)
 def assertChangeForAmountIs(self, changer, amount, expected_change):
 actual_change = list(changer.change_for(amount))
 self.assertEquals(expected_change, actual_change)
 def assertChangeable(self, changer, amount):
 self.assertChangeForAmountIs(changer, amount, [True])
 def assertNotChangeable(self, changer, amount):
 self.assertChangeForAmountIs(changer, amount, [])

Answer 1

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:

1. collections of denominations of coins (represented by lists of numbers); and
2. caches of previously computed results (represented by dictionaries).

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

2. Other review comments

1. 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.

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

3. 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?

4. 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.

5. 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.

6. 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.

3. 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.

4. 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 <= n:
 for p in partitions(n - first, values):
 yield (first,) + p
 yield from partitions(n, values[1:])
@lru_cache(maxsize=None)
def count_partitions(n, values):
 """Return the number of ways of expressing n as a sum of items from
 the tuple values (with repetition, ignoring order).
 >>> # 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 <= n:
 count += count_partitions(n - first, values)
 return count
def partitionable(n, values):
 """Return True if it is possible to express n as a sum of items from
 the tuple values (with repetition).
 >>> partitionable(11, (4, 5))
 False
 >>> partitionable(59, (6, 7))
 True
 """
 return any(True for _ in partitions(n, values))

Notes:

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

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

3. 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.

5. 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))]