;; some probability theory stuff
(module prob mzscheme
  (require (lib "list.ss"))

  (provide (all-defined))


  (define (fact n)
    (if (< n 0) (error "FACTORIAL: can't take in negative number ~s" n))
    (let loop ((n n) (r 1))
      (if (= n 0)
          r
          (loop (sub1 n) (* r n)))))


  (define (perm n k)
    (/ (fact n) (fact (- n k))))
  

  (define (choose n k)
    (/ (fact n) (* (fact k) (fact (- n k)))))


  ;; randomize a list.  We do this by decorate/sort/undecorate.
  (define (shuffle l)
    (let ((decorated-list (map (lambda (x) (cons (random) x)) l)))
      (let ((sorted-listpairs (quicksort decorated-list
                                         (lambda (a b) (< (car a) (car b))))))
        (map cdr sorted-listpairs))))


  ;; Sample n elements out of list l.
  (define (sample l n)
    (when (< (length l) n)
      (error "SAMPLE: can't sample ~s elements of l, which only has ~s"
             n (length l)))
    (slice-first-n (shuffle l) n))


  ;; slices out the first n elements of l.
  (define (slice-first-n l n)
    (cond ((= n 0) '())
           ((null? l) '())
           (else (cons (car l) (slice-first-n (cdr l) (sub1 n))))))


  ;; Creates a n-length list of x.
  (define (repeat x n)
    (if (= n 0) '()
        (cons x (repeat x (sub1 n)))))

  
  ;; The birthday paradox: Given a room full of 'k' people, tells us
  ;; the probability of at least two people sharing a birthday.  The
  ;; assumption is that the year is 365 days.
  (define (birthday k)
    (- 1.0 (/ (fact 365) (* (fact (- 365 k)) (pow 365 k)))))
  
  )