CMPU-145, Spring 2013
Asmt. 5
Due:  Monday, April 22 @ 1:30 p.m.

    Begin by downloading the file "asmt5-helper.txt" from the asmt5
    directory.  Be sure to include the following expression near the
    top of your definitions file:

        (load "asmt5-helper.txt")

    The functions defined in "asmt5-helper.txt" will be used in Problem 3.

======================================

PROBLEM 1. 

  Define a function, called GEN-ALL-PERMS, that takes a list of items
  as its only input.  (You may assume that the input list does not
  contain any duplicates.)  It should return as its output a list of
  all *permutations* of the input list, where each permutation
  contains *all* of the elements of the input list, but possibly in a
  different order, as illustrated below.

      > (gen-all-perms '(1 2))
      ((1 2) (2 1))
      > (gen-all-perms '(1 2 3))
      ((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))
      > (length (gen-all-perms '(1 2 3 4)))
      24
      > (length (gen-all-perms '(1 2 3 4 5)))
      120

    NOTE:  For permutations:  ORDER MATTERS and REPETITION is NOT allowed.

    NOTE:  For testing, notice that the number of permutations of
           a list of length N is Perm(N,N) = N!

    NOTE:  There are many ways to solve this problem.  

    HINT:  Let recursion work for you!!  Let MAP work for you!!

    HINT:  Suppose ITEM is one of the elements of LISTY (not
           necessarily the first).  How could you generate all
           permutations of LISTY that have ITEM as their first
           element?
           
	   For example, suppose LISTY = (a b c d) and ITEM = c.

           What recursive function call of GEN-ALL-PERMS might be useful?

           Note that there's a built-in function REMOVE that removes a
	   given item from a list: (remove 'c '(a b c d)) ==> (a b d).

======================================
           
PROBLEM 2.

  Recall that for COMBINATIONS, order does NOT matter and repetition
  is NOT allowed.  For this problem, define a function called
  GEN-ALL-WAYS-OF-CHOOSING-K-ITEMS, that takes two inputs: LISTY and
  K, where LISTY is a list of items (no duplicates) and K is a
  non-negative integer.  It should return as its output a list of all
  the possible ways of choosing K items from LISTY, as illustrated
  below.

      > (gen-all-ways-of-choosing-k-items '(1 2 3) 1)
      ((1) (2) (3))
      > (gen-all-ways-of-choosing-k-items '(1 2 3 4) 2)
      ((1 2) (1 3) (1 4) (2 3) (2 4) (3 4))
      > (gen-all-ways-of-choosing-k-items '(1 2 3 4 5) 3)
      ((1 2 3) (1 2 4) (1 2 5) (1 3 4) (1 3 5) (1 4 5) (2 3 4) (2 3 5) (2 4 5) (3 4 5))
      > (length (gen-all-ways-of-choosing-k-items '(1 2 3 4 5 6 7) 3))
      35

    NOTE:  For testing, the number of ways of choosing K items out of a
           list of length N is given by N-CHOOSE-K.  For example, in
           the last line above, the answer list contains 7-choose-3 =
           35 entries.

    HINT:  What should the answer be if K = 0?

           What if LISTY is EMPTY, but K > 0?

    HINT:  Think of all ways of choosing K items that INCLUDE the
           first element of LISTY versus all ways that do NOT include
           the first element of LISTY.
           
======================================

    NOTE:  In each of the following problems, your answers to parts A and B
           should be close to one another, especially if you use large 
           values of N when calling GEN-AND-TEST!

----------------------------------------
PROBLEM 3:   Poker hands with a FLUSH 
----------------------------------------

  A poker hand consists of five cards.  If all five cards have the same
  suit, then the hand is called a FLUSH.  For example, the following hand
  is a flush:

     Jack of Spades; 3 of Spades; 9 of Spades; 6 of Spades; Queen of Spades

  For this problem, you will compute the probability of getting dealt
  a 5-card hand that is a flush.  To check your work, you will also
  estimate that probability using the GEN-AND-TEST function.

  Part A.  

    Define a variable, called *NUM-FLUSHES*, whose value is the
    number of 5-card hands that are flushes (i.e., the number of
    5-card hands whose cards all belong to the same suit).

    Define a variable, called *PROB-FLUSH*, whose value is the
    probability of getting dealt a flush.  (Just divide the number
    of flushes by the number of 5-card hands.)

    Note:  The variable, *num-5-card-hands*, is defined in
    	   "asmt5-helper.txt"; so you don't have to re-define it.

    Use the TESTER function to show the value of *NUM-FLUSHES* and
    *PROB-FLUSH* in the interactions window.

  Part B.

    Define a function, called HAS-FLUSH?, that takes a list of five
    "cards" (i.e., numbers from 0 to 51) as its only input.  It should
    return #t if all of the cards in that list have the same suit.

    NOTE:  There is a SUIT function defined in "asmt5-helper.txt"
    	   that returns the suit (as a number from 0 to 3) of any
	   card.

    Next, use the GEN-AND-TEST function to estimate the probability
    of getting dealt a flush.  

    NOTE:  The RAND-POKER-HAND function, used in class, is defined 
    	   in "asmt5-helper.txt".

    NOTE:  Be sure to put your GEN-AND-TEST expression inside a 
    	   TESTER expression so that the output in the interactions
	   window is informative!


------------------------------------------------------------
PROBLEM 4:  Bridge hand with 5-4-2-2 distribution of suits.
------------------------------------------------------------

  In the game of bridge, each player is dealt a hand of 13 cards.  For
  this problem, we are interested in the distribution of suits among
  the cards in a 13-card hand.  If a hand contains 5 cards in one
  suit, 4 cards in another suit, and 2 cards in each of the remaining
  suits, then we say that that hand has a 5-4-2-2 distribution.  For
  example, a 13-card hand having 5 clubs, 4 spades, 2 hearts and 2
  diamonds is said to have a 5-4-2-2 distribution.  For this problem,
  you will compute the probability of getting such a hand dealt to
  you.

  Part A.

    Define a variable, called *NUM-HANDS-WITH-5-4-2-2*, whose value
    is the number of 13-card hands having a 5-4-2-2 distribution of
    suits (as described above).  

    Next, define a variable, called *NUM-13-CARD-HANDS*, whose value
    is the number of 13-card hands that can be dealt from a standard
    52-card deck.

    Finally, define a variable, called *PROB-5-4-2-2-DISTN*, whose
    value is the probability of getting dealt a 13-card hand having
    a 5-4-2-2 distribution.  (Just divide the previous two values.)

    Use the TESTER function to display the values of these variables.

  Part B.

    Define a function, called GEN-BRIDGE-HAND, that takes no inputs.
    It should return as its output a randomly generated list of 13
    cards, dealt from a standard 52-card deck.

    Define a function, called IS-5-4-2-2-DISTN?, that takes a list of
    13 "cards" (i.e., numbers from 0 to 51) as its input.  It should
    return #t if that hand of cards has a 5-4-2-2 distribution of
    suits; #f otherwise.

    NOTE:  You may wish to use the GET-HISTY functions defined in
    	   "asmt5-helper.txt".

           Here are some examples of how it works:

              > (get-histy '(1 1 2 1 5 3))
              (0 3 1 1 0 1)

           The histogram, (0 3 1 1 0 1), represents that the list, (1 1 2 1 5 3),
	   contains no 0s, three 1s, one 2, one 3, no 4s, and one 5.

           You may be interested in expressions such as the following, where
	   CARDS is a list of 13 cards (i.e., numbers from 0 to 51, inclusive):

              (get-histy (map suit cards))

           What happens if you SORT the histogram?!!


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

  When you are done...

     Turn in printouts of your definitions and interactions files.

     Submit electronically, using submit145.