Puzzle part 4 -- from theory to practice

A number of problems involve trying a value for the first element in a sequence and then recursively figuring out the rest of the sequence. Such problems are often trickier to code in C++ than they look.

One reason for the difficulty is the impulse to be efficient--by not copying data structures around unless needed. For example, suppose we use a vector to represent the denominations of stamps that we have available. It should be easy enough to try all of the possibilities for the first denomination. But how do we then manage the recursive call?

The problem devolves to passing all but the first element of a vector to a function. It happens to be our own function, but the problem is still there. When put that way, it would seem that the obvious solution is to pass a pair of iterators rather than a vector, which means yet another argument to the function.

Then there is the problem of producing output. Ideally, we would like the output for such a program to be a sequence of values for each denomination--but in order to do that, the values have to be stored in a way that can be built up one element at a time. If we're not careful, we'll wind up copying a vector each time we return from one of the recursive calls.

The first solution I sketched out was embarrassingly complicated for this reason. In particular, the function took no fewer than four arguments: (1) The number of cents to express as stamps; (2-3) two iterators representing the denominations available, and (4) an output iterator representing a place to put the counts of available stamps.

Indeed, this program was so ungainly that I am reluctant to post it here, preferring instead to look for a more elegant solution.

(To be continued...)

Posted by Andrew Koenig at 11:04 AM  Permalink