recitation 9: designing/writing the prisoner's dilemma tournament

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

Given n entries, run the 3-way tournament & print out the winner's name.

Some problems to think about:

* data structures, constructors, accessors, data abstractions
* rules of the tournament 
  - how to pick the winner
    (# of victories/losses, total score?)
  - illegal entries, errors & infinite loops
* how to come up with a list of all the matches that need to be run.
  - how many matches will we need to run?
  - what's the order of growth?
  - do we need to play all the matches or can we just play a random sample?
* does order of growth really matter?  

* what if player order mattered?  Instead of just all *combinations* of 
  3 players, we needed all *permutations* of 3 players.   Can you write
  a general permutation routine?

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

(define (all-pairs lst)
  (if (null? lst)
      nil
      (append (all-pairs (cdr lst))
	      (map (lambda (x) (list (car lst) x))
		   (cdr lst)))))

(all-pairs (list 1 2 3 4))   ->  ((3 4) (2 3) (2 4) (1 2) (1 3) (1 4))

# of pairs = n choose 2 = n * (n-1) / 2

order of growth time:  0(n^2)
order of growth space:  0(n^2)

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

(define (all-triples lst)
  (cond ((null? lst) nil)
	((null? (cdr lst)) nil)
	(else (append (all-triples (cdr lst))
		      (map (lambda (x) (cons (car lst) x))
			   (all-pairs (cdr lst)))))))
  
(all-triples (list 1 2 3 4))  ->  ((2 3 4) (1 3 4) (1 2 3) (1 2 4))

# of triples = n choose 3 = n! / (n-3)! * 3!

order of growth time: O(n^3)
order of growth space: O(n^3)

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

* write a general all-subsets function:  (all-subsets lst k)
  that returns a list of all subsets of size k.  
  (There will be "n choose k" subsets)

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

(define (all-pairs-map op lsta lstb)
  (if (null? lsta)
      nil
      (append (map (lambda (x) (op (car lsta) x)) lstb)
	      (all-pairs-map op (cdr lsta) lstb))))

(all-pairs-map + (list 10 20 30) (list 4 5 6))   ->   (14 15 16 24 25 26 34 35 36)

order of growth time: O(n*m)
order of growth space: O(n*m)

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

(define (place-at-nth lst n elt)
  (cond ((null? lst) (list elt))
	((= n 0) (cons elt lst))
	(else (cons (car lst) (place-at-nth (cdr lst) (- n 1) elt)))))

(define (integers-0-to n)
  (if (< n 0) nil
      (cons n (integers-0-to (- n 1)))))

(define (permutations lst)
  (if (null? lst)
      (list (list))
      (all-pairs-map (lambda (n sublst) 
		       (place-at-nth sublst n (car lst)))
		     (integers-0-to (length (cdr lst)))
		     (permutations (cdr lst)))))

(permutations (list 1 2 3))  ->   ((3 2 1) (2 3 1) (3 1 2) (2 1 3) (1 3 2) (1 2 3))

(permutations (list 1 2 3 4))  ->   ((4 3 2 1) (3 4 2 1) (4 2 3 1) 
                                     (3 2 4 1) (2 4 3 1) (2 3 4 1) 
                                     (4 3 1 2) (3 4 1 2) (4 2 1 3) 
                                     (3 2 1 4) (2 4 1 3) (2 3 1 4)
                                     (4 1 3 2) (3 1 4 2) (4 1 2 3) 
                                     (3 1 2 4) (2 1 4 3) (2 1 3 4) 
                                     (1 4 3 2) (1 3 4 2) (1 4 2 3) 
                                     (1 3 2 4) (1 2 4 3) (1 2 3 4))

# of permutations: n!
order of growth time: O(n!)
order of growth space: O(n!)

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