Sicp Iteration Exercise
Sicp Iteration ExerciseI'm reading the first edition of StructureAndInterpretationOfComputerPrograms, and I've come up against an exercise that I can't figure out. It's not in the second edition, but it is in the AI Technical Report (ftp://publications.ai.mit.edu/ai-publications/pdf/AITR-735.pdf [47MB!]) on the page numbered 39 in the text, page 50 of the pdf. "Design a procedure which evolves an iterative process for solving the change counting problem." They give a tree-recursive procedure for doing it on the previous page. The second edition of the book has a footnote that mentions that this can be turned into an iterative process by using memoization, but since they haven't given the reader enough tools to do memoization (assignment, state) when they ask this question in the technical report and the first edition, it seems that that can't be the solution they had in mind. I can see how to change the procedure into a linear recursive one that has just one non-tail-recursive call and one tail-recursive call by using an accumulator, but I don't see how to turn it into an iterative one.
I've tried to come up with something based on counting up the number of coins, but all of my answers end up either missing some options, or counting some options twice.
Can anyone give me a hint? Thanks.
I did it! I'm the same person who posted this question years ago. I just came back to the problem and this time I found an answer using only the techniques that had been introduced at that stage of the book.
My confusion came from a modification I made to the function. In the old discussion below, I generalized it by using an arbitrary list of coin values. In SICP, they used a numeric argument from 0 to 5 to indicate which coin type was being operated on, which was transformed into a coin value by a separate function.
Here is the original SICP code:
(define (count-change amount) (cc amount 5)) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (= kinds-of-coins 0)) 0) (else (+ (cc (- amount (first-denomination kinds-of-coins)) kinds-of-coins) (cc amount (- kinds-of-coins 1)))))) (define (first-denomination kinds-of-coins) (cond ((= kinds-of-coins 1) 1) ((= kinds-of-coins 2) 5) ((= kinds-of-coins 3) 10) ((= kinds-of-coins 4) 25) ((= kinds-of-coins 5) 50)))The key observation that finally made it click for me was that since there are only 6 values for kind-of-coins, one could split cc into six separate functions, one for each coin type (including the 0 for none, just to be extra explicit). That can be used to turn the second recursive call, with (- kinds-of-coins 1) into just a normal function call. Then only the first recursive call is left, which can be made iterative with an accumulator.
There's plenty of room for optimization, and plenty of repeated evaluation, but all recursion is tail recursion. No memoization. No stacks. No queues. No lists of any sort, even.
Here is my answer:
(define (count-change-iter amount) (cc-fifties amount 0)) (define (cc-fifties amount acc) (cond ((= amount 0) (+ 1 acc)) ((< amount 0) acc) (else (cc-fifties (- amount 50) (cc-quarters amount acc))))) (define (cc-quarters amount acc) (cond ((= amount 0) (+ 1 acc)) ((< amount 0) acc) (else (cc-quarters (- amount 25) (cc-dimes amount acc))))) (define (cc-dimes amount acc) (cond ((= amount 0) (+ 1 acc)) ((< amount 0) acc) (else (cc-dimes (- amount 10) (cc-nickels amount acc))))) (define (cc-nickels amount acc) (cond ((= amount 0) (+ 1 acc)) ((< amount 0) acc) (else (cc-nickels (- amount 5) (cc-pennies amount acc))))) (define (cc-pennies amount acc) (cond ((= amount 0) (+ 1 acc)) ((< amount 0) acc) (else (cc-pennies (- amount 1) (cc-nothing amount acc))))) (define (cc-nothing amount acc) acc)
"Evolves"?
The way SICP looks at things, a procedure is a dead thing, a list of instructions for the computer to execute. A process is the magic that happens when a procedure is run. A procedure "evolves" a process in the sense that the static content of the procedure causes the dynamic things in the process to happen. By "iterative process", they mean one that doesn't use more than a fixed, small amount of stack space (in SchemeLanguage, which does TailCallOptimization).
Here's the standard example:
(define (fact x) (if (= x 0) 1 (* x (fact (- x 1))))) (define (fact-iter x) (fact-iter-helper x 1)) (define (fact-iter-helper x acc) (if (= 0 x) acc (fact-iter-helper (- x 1) (* x acc))))(fact 5) will end up allocating 6 stack frames, one for (fact 5), one for (fact 4) which (fact 5) is waiting on, and so on down to (fact 0). (fact-iter 5) will only have one allocated at a time. The (fact-iter 5) frame gets tossed when the tail call is made to (fact-iter-helper 5 1), which gets tossed when the tail call is made to (fact-iter-helper 4 5), and so on down to (fact-iter 0 120) which returns 120.
In short, (fact 5) "evolves a linear recursive process", since it uses stack space linear in its argument, and (fact-iter 5) "evolves an iterative process", since it uses constant stack space, no matter how big its argument is.
So, any tips on that change counting problem?
Can you quickly define the change counting problem here ? One way to turn any recursive procedure into a tail recursive (probably that's what you mean iteratively) one is by representing the stack explicitely. Not sure that's the wanted answer though.
Given a total in cents, and a list of coin values, figure out how many ways there are to make up that amount of money using those coins.
Here is the approximate code they give, which is "tree recursive", having two non-tail calls to itself:
(define (count-change amount) (cc amount '(50 25 10 5 1))) (define (cc amount kinds-of-coins) (cond ((= amount 0) 1) ((or (< amount 0) (null? kinds-of-coins)) 0) (else (+ (cc (- amount (car kinds-of-coins)) kinds-of-coins) (cc amount (cdr kinds-of-coins))))))Here is my "linear recursive" version, which has one non-tail call to itself:
(define (count-change amount) (cc amount '(50 25 10 5 1) 0)) (define (cc amount kinds-of-coins acc) (cond ((= amount 0) (+ acc 1)) ((or (< amount 0) (null? kinds-of-coins)) acc) (else (cc (- amount (car kinds-of-coins)) kinds-of-coins (cc amount (cdr kinds-of-coins) acc)))))The objective is to come up with an "iterative" version. A CpsTransformation would make all calls into tail calls and cause the stack to be represented explicitly, but the storage used by the nested continuations would still grow linearly, so I don't think that counts as iteration. I also can't imagine that they expect someone to come up with that solution half way through the first chapter. Explicit representation of a stack is not mentioned until much later in the book, and ContinuationPassingStyle is not mentioned at all in the books that have this exercise (the second edition touches on it in the discussion of nondeterministic computing and the AmbSpecialForm).
I had a suspicion that that was the problem. Memoization means that if you do it recursively the computation say (cc 100 '(50 25)) may recursively trigger the computation of (cc 50 '(25)) twice or more (once by subtracting 100 - 50 a second time by subtracting 100 - 25 - 25 ) now imagine that the combined parameters to cc, represented the key in a dictionary or the indices in a (possibly multi-dimensional array), so the idea is to fill in the needed cells of this array so that you do not have to compute it twice.
So a trivial non-optimized procedure will start with a list of the cells to compute and a list of the cells already computed. First the "to_compute" list will have just the initial args, and the "computed" list will be empty. If you can compute directly the cell in the "to_compute" list you remove it from "to_compute" and add it to "computed" list, otherwise you prepend (or append, but prepend is better so that the CAR of the list will always be minimal with regards to the measure that determines the termination of the recursion, and be picked up in the next iteration ) the cells that prevent the computation of the current cell to "to_compute" list, and reiterate, until at some point the "to_compute" list will be empty and the initial cell will find itself in the "computed list.
So you're suggesting that the table of memoized values be part of the accumulator/accumulated state? I see how that could work, but they don't introduce cons, car, and cdr until the next chapter (instead of a list coin values, the original problem had another function that took as an argument an int from 0-5 and returned the value of the coin -- 0, 1, 5, 10, 25, 50). At the point where this question is asked, they haven't even gotten to higher order procedures. They've basically introduced naming, arithmetic, procedures, internal procedures, and recursion. Maybe the problem just can't be solved with the tools that have been introduced. I suppose that would be a good reason to take it out of the second edition. Still, I can't help thinking that there's some really simple trick that I'm missing.
In a ML like language, it will look along the lines:
let insert_result cell value list = (* ... to be defined, inserts the (cell, value ) pair in the list of computed results *) let compute_cell cell computed = (*... to be defined, computes the value of the cell, using the already computed cells returning the value or a list new cells that are needed for computing the input cell *) let F to_compute computed = match to_compute with [] -> computed | head::tail -> match (compute_cell head ) with | NeedCells? new_cells -> F (prepend new_cells to_compute) computed | Result value -> F tail (insert_result head value to_compute)I used ML because it's much more elegant for algorithms than Scheme.
An inefficient solutions (with just linear searches and comparisons to look for already computed cells) can be easily generated by a freshmen (remember this was an exercise for MIT freshmen). Now what I would call a serious exercise is to formally prove the termination of the above with the help of a proof assistant.
Even MIT freshmen can't insert "the (cell, value ) pair in the list of computed results" until they know how to use cons/car/cdr and mutate with set! or set-car!/set-cdr!. At the point where this exercise is introduced in the book, the reader who's new to scheme just doesn't have the tools to implement memoization.
(define table '()) (define (make-key amount kinds) (+ (* 10 amount) (length kinds))) (define (add! amount kinds total) (set! table (cons (cons (make-key amount kinds) total) table)) total) (define (lookup amount kinds) (assv (make-key amount kinds) table)) (define (count-change amount) (cc amount '(50 25 10 5 1))) (define (cc amount kinds-of-coins) (let ((cached (lookup amount kinds-of-coins))) (cond (cached (cdr cached)) ((= amount 0) 1) ((or (< amount 0) (null? kinds-of-coins)) 0) (else (add! amount kinds-of-coins (+ (cc (- amount (car kinds-of-coins)) kinds-of-coins) (cc amount (cdr kinds-of-coins))))))))However, this uses set!, which isn't introduced until chapter 3. This exercise is half way through chapter 1.
All righty. Here's a purely functional version that uses memoization. It's not particularly efficient. However, in implementing this I had to use trace to debug it and I noticed something (see below).
(define (make-key amount kinds) (+ (* 10 amount) (length kinds))) (define (extend-cache amount kinds value cache) (cons (cons (make-key amount kinds) value) cache)) (define (lookup amount kinds cache) (assv (make-key amount kinds) cache)) (define make-state cons) (define state-count car) (define state-cache cdr) (define (count-change amount) (state-count (cc amount '(50 25 10 5 1) (make-state 0 '())))) (define (cc amount kinds-of-coins state) (let ((cached (lookup amount kinds-of-coins (state-cache state)))) (cond (cached (make-state (+ (cdr cached) (state-count state)) (state-cache state))) ((= amount 0) (make-state (+ (state-count state) 1) (state-cache state))) ((or (< amount 0) (null? kinds-of-coins)) state) (else (let ((ret (cc amount (cdr kinds-of-coins) (cc (- amount (car kinds-of-coins)) kinds-of-coins state)))) (make-state (state-count ret) (extend-cache amount kinds-of-coins (- (state-count ret) (state-count state)) (state-cache ret))))))))What did I realize? This is still linear recursive! So is the memoized version above which uses state! I just looked at the second edition footnote again, and it says "Tabulation can sometimes be used to transform processes that require an exponential number of steps (such as count-change) into processes whose space and time requirements grow linearly with the input." Note the grow linearly part. This still isn't an answer to the original exercise. The original exercise says to find an iterative version.
I'm going to quote the SiCp definition of an iterative process:
In general, an iterative process is one whose state can be summarized by a fixed number of variables, called state variables, together with a fixed rule that describes how the state variables should be updated as the process moves from state to state, and an (optional) end test that specifies conditions under which the process should terminate.
The memoized version, compared to my first "linear recursive" version above, may take linear time instead of exponential (an improvement), but it still takes linear space.
Aside from the fact that a memoized version seems beyond the techniques presented in the first half of chapter 1, it also isn't the right answer.
I suspect that the right answer requires an entirely different approach. Maybe a counter that runs from 1 up to the number of cents, or a deep insight that reduces the whole thing to a few cool formulas.
Arggh, you haven't tried to follow exactly the ML pseudo-code, plus you went into premature optimization, by encoding the cell which is a pair of (sum . lits-of-coins) into an integer, thus detracting from the clarity of the algorithm. I have now the Scheme code ready and tested along the lines of ML code -- just for having fun and proving to myself that I wasn't talking non-sense. Following the ML code makes it real easy, although Scheme notation is arguably less elegant and more error prone because of wildly dynamic typing.
Now if you are not a student with a real assignment, I'll post the code here, otherwise it would be unethical to help you with more than directions to follow. If this "homework" is just about you having fun trying to do more than what is required at school, then I can put the code right here. --CostinCozianu
This is not a class assignment. I am not a student, but I do work at a university IT department, which is why my address ends in ".edu". If you think you can get a bounded amount of memory usage with memoization, I am very curious as to how. I just don't see how any memoizing solution will use the same amount of memory for (count-change 10000) as it would for (count-change 100).
On a happier note, I have found a solution which I think is iterative. It is based on a different algorithm, but seems to give the same answers in my tests.
(define (make-tail length item) (if (= length 1) (list item) (cons 0 (make-tail (- length 1) item)))) (define (advance-state amounts kinds) (cond ((null? amounts) '(0)) (else (let* ((res (advance-state (cdr amounts) (cdr kinds))) (subtot (car res)) (sublis (cdr res))) (cond ((not subtot) (cons #f (cons (car amounts) sublis))) ((>= subtot (car kinds)) (cons #f (cons (+ (car amounts) 1) (make-tail (length sublis) (- subtot (car kinds)))))) (else (cons (+ (* (car amounts) (car kinds)) subtot) amounts))))))) (define (count-change amount) (cc (list 0 0 0 0 amount) '(50 25 10 5 1) 1)) (define (cc amounts kinds total) (let* ((res (advance-state amounts kinds)) (flag (car res)) (next-amounts (cdr res))) (if flag total (cc next-amounts kinds (+ total 1)))))In the above cc is tail-recursive, but advance-state is not as it calls itself in the let* ((res (advance-state (cdr amounts) (cdr kinds)) ... . I'll try later to understand your solution, but can you explain it a little bit ?
The basic idea is for "amounts" to hold every possible breakdown in turn, while "total" is bumped up by one each time:
(0 0 0 0 100) (0 0 0 1 95) (0 0 0 2 90) ... (0 0 0 20 0) (0 0 1 0 90) (0 0 1 1 85) (0 0 1 2 80) ... (0 0 1 18 0) (0 0 2 0 80) ... (2 0 0 0 0)advance-state returns a cell whose car is either #f, or the monetary value of its cdr. The car is #f if it has made a state change, and a monetary value if it has not. This is used by cc to decide whether it has reached the last state. It is also used by advance-state in the recursion. The idea is that I want to bump up the count on the least value coin that I can by one, and turn everything below it back into pennies. The work is done while unwinding the calls to advance-state. The base case returns (0), which represents a total of 0 made up of no coins. After making the recursive call, the question is, has the state-advancement been done in a lower denomenation yet or not? If it has, this is the (not subtot) case, and all that needs to be done is for the count of the current coin (car coins) to be added to the beginning of the cdr to return. If it has not, check to see if the total value of the smaller coins is greater than or equal to the value of one of the current coins - (>= subtot (car kinds)). If so, we are at the bump. Add one to the count of the current coin, reduce what's left of the remaining total back to pennies (the make-tail call), add the #f to signal that we did the state change, and return. If not, nothing can be done yet, so add the current coin count*value to the total, add the current coin count to the beginning of the coin list, and return.
Of course, not a fixed amount of memory as the list used for memoization grows butthe amount of memory will be linear with the size of the problem. Here's the solution derived from the above pseudocode in ML. In Scheme it looks worse, but then I don't program Scheme for a living.
A cell is a pair (value . coin-list) that defines an instance of the coin-problem. for example (10 . (5 2 1) ) is the problem of making up 10$ with coins of 5,2 and 1. compute-for-cell tries to get the solution for the cell based on previously computed cells, or if it fails it returns the cells that are missing from computed cells in order for the result to be computable. The rest is straightforward.
I also need to state the assumption that the list of coins is given in descending order.
(define (make-cell sum coin-list) (cons sum coin-list)) ; tries to compute for the cell based on already computed cells ; returning either the result if this can be obtained ; or the list of more cells that are needed to be computed ; before the argument can be computed (define ( compute-for-cell cell computed-list) ( let ((value (car cell)) (coin-list (cdr cell))) (cond ((= value 0) 1) ; we subtracted just the right amount ((< value 0) 0) ; we subtracted too much (else (if (null? coin-list)As you can see the only recursive function is memo-count and it calls itself in tail position only. I'm thinking though that Scheme is a not so great language for teaching algorithms to beginners, it's also an aquired taste, and although i aquired it, I'm still sometimes dissatisified with how my Schme programs look. --CostinCozianu(let* ((first-coin (car coin-list)) (cell1 (make-cell (- value first-coin) coin-list)) (cell2 (make-cell value (cdr coin-list))) (cell1R (assoc cell1 computed-list)) (cell2R (assoc cell2 computed-list)) ) (if (and cell1R cell2R) ; both recursive cells were computed previously (+ (cdr cell1R) (cdr cell2R)) ; return an integer -- the result for the cell ;otherwise returns the list of cells that we need (if (not cell1R) (cons cell1 (if cell2R '() (list cell2))) (list cell2)) ) )))))) (define (memo-count to-compute computed) (if (null? to-compute) computed (let* ((head (car to-compute)) (headR (compute-for-cell head computed))) ; the result for count(head) if it exists (if (integer? headR) ; we have a real result put it in the right list (memo-count (cdr to-compute) (cons (make-cell head headR) computed)) ; else we have more cells to compute, prepend them on the left list (memo-count (append headR to-compute) computed)) ))) (define (coin-count value coin-list) (let ((cell (make-cell value coin-list))) (cdr (assoc cell (memo-count (list cell) '())))))
- ; no more coins
Oooo... very clever. So the real work is in building up the cache, with to-compute acting as a stack. Then you just use the created cache. I like it.
I still can't help but feel like I'm missing something. Although I like my latest solution, and yours, neither one seems to quite fit the bill. Ah well, it's still fun to wonder.
Pretty problem. It is easy to compute the values for pennies, nickels and dimes directly, with no recursion at all. Off hand, I don't see an easy way to do this for quarters and half dollars. (I'd be interested to know if anyone sees a way to do this.) If this is done, then the recursion depth for the quarters/50 cent pieces is only 2 or 3, I think, which is vastly improved over the recursive version, and arguably more efficient in terms of both time and space over memoization. Perhaps they were thinking of something along these lines - it certainly doesn't need car, cdr and friends. sdb
How do you compute it directly for pennies, nickels and dimes? I've tried to do that, but I've had trouble finding a formula that doesn't count 5 pennies, one nickel and one nickel, 5 pennies as separate cases.
I gather you already noticed that this thing has a granularity of 5. The number of coins changes every nickel, in other words. You don't use probability formulas, which it sounds like you are doing. Just some simple combinatorics. There is always only 1 way to change using a penny, amount/5 ways to change using a nickel. floor(amount^2/4) ways to change using dimes.
Quarters were harder, but I now have a completely iterative version. Once you have quarters, 50 cents is a gimme, since the values just repeat (except for the last, which you can just special case). If you want, I can email you the program, but since you asked for hints, not a solution, I don't want to steal your fun away. If you want it, drop me a note at my initials AT ssr DOT com.
Thanks again for this most interesting problem. I suspect there must be a way to compute the whole thing directly, but when I tried, I got a very hairy expression which I gave up on. My combinatorics are a little rusty, I guess.
sdb
Still trying to understand the pennies, nickels, and dimes, it seems to me that there are 4 ways to change 10 cents (1 dime, 2 nickels, 1 nickel+5 pennies, and 10 pennies). Yet floor(10^2/4) = 25. What am I missing?
I don't think "sdb" is right in the details, but in the large I think he is right: given a list of coins a1,a2, an such that aj divides a(j+1) then we should be able find a combinatorial formula that will allow us to calculate the number of possibilities directly without hunting for the actual solutions. Now I'm, at work now so I cannot come up quickly with it, but this should be a good challenge. But as soon as you get something like 10c and 25c then we're back to the recursion above. --Costin
My mistake, sorry. Here are the formulas I use:
Pennies: always returns 1
Nickels: amount/5
Dimes: floor((amount/5)^2/4) (the "amount/5" was omitted from my earlier note, sorry about that).
Quarters are harder, and gave me some trouble. But it turns out the successive differences between the amounts of the quarters form a nice sequence, the nth term of which is given by round( (sequence+4)^2/20). Here is the code:
(define (wtc-quarters amount)
(define (doit-iter change sequence fence) (cond ((= fence amount) change) (else (doit-iter (+ change (round (/ (square (+ sequence 4)) 20)) (+ sequence 1) (+ fence 5))))) (if (< amount 25)
(doit-iter 1 1 25)))the same sequence is followed for 1/2 dollars, except for the case when amount=100.
The calling procedure just needs to make sure to round down to the nearest multiple of 5 before computing any of these, the code above assumes that.
(define (cc-iter amount)
(define (doit normed) (+ (wtc-halfdollar normed) (wtc-quarters normed) (wtc-dimes normed) (wtc-nickels normed) (wtc-pennies normed))) (if (> amount 4) (doit (* (floor (/ amount 5)) 5)) (doit amount)))or something along these lines.
"sdb"
Still trying to understand the dimes here... It seems to me that applying floor((amount/5)^2/4) to 10 gives 1 instead of 4, like it should. Could I trouble you to try and explain how that formula is supposed to work?
The functions return the number of ways to make change using that particular coin, not the total number of ways to make change with and without that coin.
I.E. There is only one way to change 10 cents using a dime, so the dime function returns 1. There are two ways to change 10 cents with nickels (two nickels, and one nickel and five pennies). So (10/5) = 2. And there is only one way to change any amount with pennies, which is 1. There are zero ways to change 10 cents with half-dollars and quarters. Therefore,
HD(10)+Q(10)+D(10)+N(10)+P(10) = 0 + 0 + 1 + 2 + 1 = 4, which is the number you are looking for.
This last sum is the equivalent of the (+ (wtc-pennies amount) (wtc-dimes amount) (wtc-mumble amount)) in cc-iter, above.
"sdb"
If anyone is still interested in this problem, I found an answer I think. I was teaching a course, and I gave the same problem to my class but denominated in RMB. Many of my students surprised me by producing iterative Java solutions, and I wanted to convince my students that recursion could handle problems as efficiently as iteration. When I started thinking about the problem, I tried to visualize the tree generated by the tree recursion in the recursive solution. A path through the tree should be ordered with choices of one type of coin followed by the next type until you work your way to the end of the selection of coins. So at a leaf in the tree, where we count, we need a list of the number of path components for each choice of coin. We need a state element to hold results. So we call functions with an amount, a list of lengths of paths for each coin preceding the last coin, and a result. Each node in the tree first calls its right child representing the case of no coins of the type of the caller and having responsibility for calling the parent function back with results. A node then continues down the left branch updating the list of path choices and the amount. Each recursive call is a tail call, so the execution should use constant stack space. I think that the amount of data stored depends only on the number of coins and not the depth of the tree. My program follows.
(define noFives
(lambda (amount order result) (let ((newresult (+ result 1))) (noTens amount order newresult))))(define noTens
(lambda (amount order result) (if (= (length order) 5) (if (< amount 5) (noTwenties (+ amount (* (car order) 5)) (cdr order) result) (noFives (- amount 5) (cons (+ (car order) 1) (cdr order)) result)) (noFives amount (cons 0 order) result))))(define noTwenties
(lambda (amount order result) (if (= (length order) 4) (if (< amount 10) (noFifties (+ amount (* (car order) 10)) (cdr order) result) (noTens (- amount 10) (cons (+ (car order) 1) (cdr order)) result)) (noTens amount (cons 0 order) result))))(define noFifties
(lambda (amount order result) (if (= (length order) 3) (if (< amount 20) (noHundreds (+ amount (* (car order) 20)) (cdr order) result) (noTwenties (- amount 20) (cons (+ (car order) 1) (cdr order)) result)) (noTwenties amount (cons 0 order) result))))(define noHundreds
(lambda (amount order result) (if (= (length order) 2) (if (< amount 50) (noLimits (+ amount (* (car order) 50)) (cdr order) result) (noFifties (- amount 50) (cons (+ (car order) 1) (cdr order)) result)) (noFifties amount (cons 0 order) result))))(define noLimits
(lambda (amount order result) (if (= (length order) 1) (if (< amount 100) result (noHundreds (- amount 100) (cons (+ (car order) 1) (cdr order)) result)) (noHundreds amount (cons 0 order) result))))(define count-change (lambda (amount) (noLimits amount '() 0)))
Thanks, Joseph Kulisics, kulisics@alumni.uchicago.edu
CategoryFunctionalProgramming CategoryScheme
Essentially,i think it's a two-dimensional recursion equation,look at exercise 1.10, it's clearer.i guess,computing a n-dimensional recursion equation f(x1,x2..,xn) need at least space of O(x1)*O(x2)..*O(x(n-1)) .Just guess ,i can't prove it.
The problem can be solved in linear time, constant space. The key is properly caching past counts. My first cut solution stored all past counts in a table where row=amount and column=denomination-subsets. The first row is the most recent, and the first column stores counts that include all denominations. The table is built right->left and top->bottom. This way the tree-recursive version...
(define a 100)
(define d (list 50 25 10 5 1)) ;the list of denominations is arbitrary as long as they are sorted natural numbers
;simple algorithm with exponential complexity
(define (count-tree a d)
(cond ((= a 0) 1)
((or (< a 0)
(null? d)) 0)
(else (+ (count-tree (- a (car d)) d);will be cached in an earlier row
(count-tree a (cdr d))))));will be cached in an earlier column, same row
...becomes iterative in amount and linear-recursive in the denomination set:
;count upwards caching the results, O(len(d)*a) in space and time
(define (count-linear a d)
(let increment ((acc 1)
(cache '()))
(let ((row (let new-row ((ds d)) ;ds is the sublist of denominations
(if (null? ds) '()
(let ((tail (new-row (cdr ds)))) ;tail is generated as stack unrolls
(cons (+ (cond ((< acc (car ds)) 0)
((= acc (car ds)) 1)
(else (list-ref ;reference previous values for efficiency
(list-ref cache (- (car ds) 1))
(- (length d) (length ds)))))
(if (null? tail) 0 ;combinations without current-highest
(car tail))) ; denomination
tail))))))
(cond ((> acc a) #f) ;this should only happen if a is not a natural number
((= acc a) (car row));value in newest row corresponding to all denominations
(else (increment (+ acc 1)
(cons row cache))))))) ;add current row to the cache
(I didn't restrict myself to the subset of Scheme that SICP had taught up the this point.) Now looking at where I reference the cache, I notice that the furthest row I look up corresponds to the largest denomination. That means that with US coins, I only have to store 50 rows of cache. If the cache gets bigger, I can pop off the last element. The code should be identical except for the end, but it will execute with constant space and linear time as the amount increases. I'm pretty sure that's as good as it gets, although my implementation could likely use some streamlining.
;use a queue of rows for the cache to get constant space, linear time
(define (count-iterative a d)
(let increment ((acc 1)
(cache '()))
(let ((row (let new-row ((ds d)) ;ds is the sublist of denominations
(if (null? ds) '()
(let ((tail (new-row (cdr ds)))) ;tail is generated as stack unrolls
(cons (+ (cond ((< acc (car ds)) 0)
((= acc (car ds)) 1)
(else (list-ref ;reference previous values for efficiency
(list-ref cache (- (car ds) 1))
(- (length d) (length ds)))))
(if (null? tail) 0 ;combinations without current-highest
(car tail))) ; denomination
tail))))))
(cond ((> acc a) #f) ;this should only happen if a is not an integer
((= acc a) (car row));value in newest row corresponding to all denominations
(else (increment (+ acc 1)
(cons row (if (< (length cache) (car d)) cache ;pop last element
(begin (let pop-back ((x cache)) ; of cache when it
(if (null? (cddr x)) ; has reached full
(set-cdr! x '()) ; size
(pop-back (cdr x))))
cache)))))))))
(This is my first time adding content, so feel free to correct any formatting/etiquette mistakes.)
EditText of this page
(last edited February 24, 2014)
or FindPage with title or text search