Programming Praxis

We’ll look first at the standard closed-form solution. The (choose n r) function calculates the number of ways to choose r items from a group of n items:

(define (choose n r)
  (let loop ((n n) (r r) (c 1))
    (if (zero? r) c
      (loop (- n 1) (- r 1) (* c n (/ r))))))

There are 27C3 ways to choose three people from a group of twenty-seven. (That 27C3 is the notation used in my daughter’s high-school textbook. When I was in high school, the notation was .) Of those, 24C2 will have one person with green eyes (that is, choose two of the twenty-four people who don’t have green eyes). Since any of the three can have green eyes, the result must be multiplied by three:

> (* (/ (choose 24 2) (choose 27 3)) 3)
92/325

There are 27C3 = 2925 possible sets of three people, of which 3 × 24C2 = 828 have one person with green eyes. The fraction 828/2925 reduces to 92/325, or 28.3%.

We could instead enumerate all 2925 collections of three people and count those that have one person with green eyes. Here we define a vector of length twenty-seven with the appropriate mix of blue, brown and green:

(define eyes (make-vector 27 'blue))
(for (i 0 3) (vector-set! eyes i 'green))
(for (i 3 16) (vector-set! eyes i 'brown))

We also need a function that checks the color of a person’s eyes:

(define (green x)
  (if (eq? (vector-ref eyes x) 'green) 1 0))

Now we form the 2925 possibilities and count how many have one person with green eyes:

> (length
    (list-of (list a b c)
      (a range 0 27)
      (b range (+ a 1) 27)
      (c range (+ b 1) 27)
      (= (+ (green a) (green b) (green c)) 1)))
828

A third approach is to simulate a large number of selections from appropriate groups of people and count those that have one person with green eyes. We need to select three persons from a population of twenty-seven, or more generally m items from a set of n, without replacement. We can make the selection by running through the items x in order, selecting each with probability ^s/_r, where s is the remaining number of items to be selected and r is the remaining number of items in the selection pool (this is Knuth’s algorithm 3.4.2S):

(define (sample n m)
  (let loop ((s m) (r n) (x 0) (xs '()))
    (cond ((= x n) xs)
          ((< (rand) (/ s r))
            (loop (- s 1) (- r 1) (+ x 1) (cons x xs)))
          (else (loop s (- r 1) (+ x 1) xs)))))

Then we can simulate n tests:

(define (sim n)
  (define (s?)
    (= (sum (map green (sample 27 3))) 1))
  (let loop ((n n) (g 0))
    (if (zero? n) g
      (loop (- n 1) (+ g (if (s?) 1 0))))))

Here’s a sample:

> (sim 2925)
827

That our sample run randomly gave an answer so close to the true answer is an example of sheer dumb luck. Math problems like this let us show off the Standard Prelude; we used sum, for, list-of, and rand. You can run the program at http://codepad.org/gSUgP0pn.

Pages: 1 2