CMPU-145, Spring 2013
Lab 7
April 8, 2013


Recall the definition of the POWER function seen in class today.

  (define power-acc
    (lambda (x n acc)
      (cond
        ;; Base Case:  N = 0
        ((<= n 0)
         ;; Return the accumulated answer
         acc)
        ;; Recursive Case:  N > 0
        (#t
         ;; Tail-recursive function call with new inputs
         (power-acc x 
                    (- n 1) 
                    (* acc x))))))

  (define power
    (lambda (x n)
      (power-acc x n 1)))

Notice that it uses an accumulator-based helper function to "accumulate"
the desired answer.  The POWER function itself is just a wrapper function
that calls the helper function with a suitably initialized accumulator.

  > (power 3 2) 
  9
  > (power 2 3)
  8

For the first two problems in this lab, you will define some useful
functions for permutations and combinations using similar
accumulator-based techniques.


PROBLEM 1:  PERMUTATIONS ---  Order matters, Repetition not allowed

  The number of ways of selecting K items out of N where order matters
  and repetition is not allowed is PERM(N,K) = N!/(N-K)!  For example,
  PERM(5,2) = 5!/(5-2)! = 5!/3! = 5*4.  Similarly, PERM(10,4) =
  10!/(10-4)! = 10!/6! = 10*9*8*7.

  Notice that the product, PERM(10,4), contains 4 factors, starting
  with 10.  Similarly, PERM(5,2) contains 2 factors, starting with 5.
  In general, PERM(N,K) contains K factors, starting with N.

  Therefore, rather than computing N! and (N-K)! and then dividing, it
  is much more efficient to simply compute the product of the K
  factors.  

  Define a function called PERMY that takes two inputs, N and K.  It
  should return as its output the product, N*(N-1)*...*(N-K+1), which
  has K factors starting at N.  

  Define an accumulator-based helper function, PERMY-ACC, that takes
  an extra input, ACC, that "accumulates" the desired answer.  PERMY
  should just call the helper function with a suitably initialized
  accumulator.

    > (permy 6 2)    ;;  = 6*5
    30
    > (permy 6 3)    ;;  = 6*5*4
    120


PROBLEM 2:  COMBINATIONS ---  Order doesn't matter, Repetition not allowed.

  The number of ways of selecting K items out of N where order doesn't
  matter and repetition is not allowed is COMB(N,K), also called
  "N choose K".

  Notice that N-choose-K = N!/[(N-K)!K!] = N*(N-1)*(N-2)*...*(N-K+1)
                                           -------------------------
                                           K*(K-1)*(K-2)*...* 1

  Notice that the numerator is the product of K factors, starting at N,
  and the denominator is the product of K factors, starting at K.

  Thus, the value N-choose-K can be efficiently "accumulated" as follows:

     [N/K] * [(N-1)/(K-1)] * [(N-2)/(K-2)] * ... * [(N-K+1)/1]

  Notice that the above expression is a product of exactly K factors.
  The factors happen to be fractions, but that's okay.  So, define a
  function called N-CHOOSE-K that takes two inputs, N and K.  It
  should return the value "N choose K" discussed above.  It should
  call an accumulator-based helper function, N-CHOOSE-K-ACC, that
  incrementally computes the above quantity, one FACTOR at a time.

    > (n-choose-k 6 2)      ;;  = (6/2)*(5/1) = (6*5)/(2*1) 
    15
    > (n-choose-k 6 3)      ;;  = (6/3)*(5/2)*(4/1) = (6*5*4)/(3*2*1)
    20


PROBLEM 3.  

  Define a function called RAND-CHOOSE-ONE that takes a list as its
  only input.  You may assume that the list has no duplicate items.
  The function should return one of the items from the input list,
  chosen at random.

    HINT:  Use the built-in functions:  LENGTH, RANDOM and NTH.

           The behavior of the NTH function is shown below.

             > (nth '(a b c) 0)
             a 
             > (nth '(a b c) 1)
             b
             > (nth '(a b c) 2)
             c

           Notice that the indices go from 0 to N-1, where N is the
           length of the list.  Hey, that works well with the numbers
           returned by the RANDOM function!

      Recall that an expression (random n) evaluates to a random
      number in the the {0, 1, 2, ..., n-1}.  For example, (random 3)
      will evaluate to one of the numbers in the set {0, 1, 2}.

    ==> Make sure that your RAND-CHOOSE-ONE function, when run repeatedly,
        eventually chooses each item in the list, as illustrated below.

          > (rand-choose-one '(a b c d))
          c
          > (rand-choose-one '(a b c d))
          c
          > (rand-choose-one '(a b c d))
          a
          > (rand-choose-one '(a b c d))
          d
          > (rand-choose-one '(a b c d))
          a
          > (rand-choose-one '(a b c d))
          b

--------------------------

When you are done, ask one of the coaches to check out your work.

Then submit electronicaly as usual.