Part C: Numeric Recursion and
Analysis
Euler and
Galois had
lunch in Grinnell last week, and both were intrigued by the Stir Fry
counter. On this particular day, one could select from a choice of
five vegetables: onions, mushrooms, beansprouts, scallions, and
radishes.
"I wonder how many different ways there are to select three different
veggies from this set of five," said Euler.
Being a mathematician, Galois responded: "I'd be more interested in the
general question of how many ways there are to select k different veggies
from a set of n offerings." He continued in this thought and invented a
notation. "Let's call it C(n,k)," he said, "C(n,k) is the number of ways
to choose k veggies out of a set of n."
Euler, anticipating our conventions for CSC 151, said "I'd prefer to think
like this." And he took out of his pocket an old envelope, on the back of
which he wrote:
(define combinations
(lambda (n k)
Galois said: "There are some easy cases: If n is 0 or 1 then there is
basically no choice. The number of combinations is just 1."
And Euler contributed: "And if k is 0, it's easy. There is exactly one way
to pick 0 vegetables out of a choice of n, no matter the value of n."
To which Galois added: "If k happens to be n, there is also no problem. We
must pick all of the veggies, so the number of options is also 1."
Euler said: "That's an awful lot of base cases. It's a good thing I took
CSC151 at Grinnell and know how to code recursive procedures with base
cases! But how about the recursive case(s)? How can we solve that?"
"Hmm," said Galois, "let me see: If one of the veggies is, say, onions and
we insist that we will always pick onions among our k choices, then there
will be exactly (combinations (- n 1) (- k 1)) to choose the
other k-1 veggies."
"Right!" said Euler. "And if we want to count the number of combinations
that do not include onions, then there are exactly
(combinations (- n 1) k) ways to do that. Because without
onions there are only n-1 veggies to choose from, and we still need to pick
k veggies.
After following the above conversation, please complete the
definition and documented postconditions of procedure
combinations
;;; Procedure:
;;; combinations
;;; Parameters:
;;; n, an integer
;;; k, an integer
;;; Purpose:
;;; Find the number of ways to select k items from a set of n distinct items
;;; Produces:
;;; count, an integer
;;; Process:
;;; There are several possible base cases
;;; which occur when n or k is such that there is really no choice
;;; Otherwise we need to add together
;;; the number of selections that do contain a specific object ("onions"),
;;; and the number of selections that do not contain that specific object
;;; Preconditions:
;;; n >= k >= 0
;;; Postconditions:
;;; ...?
(define combinations
(lambda (n k)
; Base case tests:
(if (or (zero? n) ; n is zero: no choice
______
______
______)
____ ; Base case value
(+ _____________________________
_____________________________))))
For example,
> (combinations 5 3)
10
> (combinations 4 2)
6
> (combinations 8 3)
56
Problem 10: Stir fry analysis
(a) Change your define combinations from question 9
to define$
combinations. Then, use the tools from
the lab on
analysis to analyze the number of times
combinations is called
in evaluating each of the expressions above. How many times is
combinations called when you invoke (combinations 20
5)?
(b) Do some more analysis of (combinations ...) and write a short
paragraph
describing your observations. Why is this or why is it not a good
program?
Optional Extra Credit (c) Euler observed to Galois: "Here's another
way to think about our stir fry lunch. For each choice of veggy:
onions, mushrooms, beansprouts, scallions, and radishes; all we have to
do to get a selection of three veggies is to pick another two veggies out
of the remaining four. Now apply that to the general problem with n and
k: For each choice of one of the n veggies it remains to pick k-1 out of
the remaining n-1. Doesn't this suggest that C(n,k) = n * C(n-1,k-1)?"
So Euler wrote the following code:
;;; Procedure:
;;; combinations2
;;; Parameters:
;;; n, an integer
;;; k, an integer
;;; Purpose:
;;; Find the number of ways to select k items from a set of n distinct items
;;; Process:
;;; This code contains an error. It is based on Euler's mistaken observation
;;; that the number of combinations of k items from a set of n is going to
;;; be n times the number of combinations of k-1 items from a set of size
;;; n-1
;;; Base cases occur when n or k is 0
;;; Produces:
;;; count, an integer
;;; Preconditions:
;;; n >= k >= 0
;;; Postconditions:
;;; ...?
(define combinations2 ;;; This code is incorrect
(lambda (n k)
(cond
((zero? (* n k)) 1)
(else (* n (combinations2 (- n 1) (- k 1)))))))
"Almost," said Galois. "But you're overcounting if you do that. Each
combination of k veggies gets counted several times. To get the correct
recurrence you need to modify your recurrence C(n,k) = n * C(n-1,k-1) to
take into account that each combination is counted that many times on the
right hand side. You need to divide the right hand side by the number of
times each combination is counted to obtain the correct recurrence."
Galois is right. Confirm that the code given above gives wrong
answers. For extra credit, correct the code for
combinations2. Then change the define to
define$ and perform an analysis of how well the new code
performs. Finally, write a paragraph based on your analyses
explaining which of combinations or
combinations2 you prefer and why.
This work is licensed under a
Creative Commons Attribution-NonCommercial 2.5 License
.