;; generate all possible perumations of a list of numbers (a set of numbers)
;;
;; assumption is that no two numbers are the same!
;;

;; general strategy:
;;  1. generate all possible permutations that keep the first number fixed.
;;  2. generate all possible permutations that have something else for the
;;     first number.
;;  append lists produces by 1. and 2.
;;
;;
;;  1.1 need to generate all permutations of the rest of the list,
;;   and then add element to the beginning of each of the lists produced.
;;   add-element-to-lists is defined below:


;;
;; add-element-to-lists consumes a number and a list of lists,
;;  and produces a list of lists.
;;
;; (add-element-to-lists elem lists) creates a list of lists, containing
;; one entry for each list found in lists (each element of lists is a list of 
;;  numbers). Each list generated gets elem tacked on the beginning of it.
;;
(define (add-element-to-lists elem lists)
  (cond 
   [(empty? lists) empty]
   [ else
	 (cons 
	  (cons elem (first lists))
	  (add-element-to-lists elem (rest lists)))]))

;;
;; 2. strategy is to step through the original list, picking each element 
;;  and generating all permutations that start with that element.
;;  


;; generates all permutations that start with f  fixed 

;; (generate-permutations alist) consumes a list of numbers and produces
;;  a list of lists of numbers. Each list of numbers is unique in the
;;  ordering of elements, each list of numbers contains exactly the same
;;  numbers as are found in alist.
;;
;; sample: (generate-permutations '(1 2 3))
;;
(define (generate-permutations alist)
  (cond
   ;; empty list has no permutations, but we need to return a list)
   [(empty? alist) (list empty)]
   ;; single element has only one permutation, but we need to
   ;;  return a list of lists.
   [(empty? (rest alist)) (list alist)]
   [ else
	 ;; more than one element - generate all lists by generating
	 ;; the lists (permutations) that start with each element in turn
	 (use-each-element-as-start alist)]))


;;
;; use-each-element-as-start consumes a list and produces a list of
;; lists of numbers. 
;;
;; (use-each-element-as-start alist) basically does the whole job, but does so
;; only by calling the helper function which deals with two lists
;;  (initially one of them is empty).

(define (use-each-element-as-start alist)
  (use-each-element-as-start-helper empty alist))


;;
;; use-each-element-as-start-helper consumes two lists of numbers 
;;    and returns a list of lists of numbers
;;
;; (use-each-element-as-start-helper done remaining) generates all
;; permutations of the elements defined in the two lists combined,
;;  such that the first element in the permutation is found in the list
;;  named remaining. Calls itself recursively to step over all the elements
;;  in remaining.
;;
;;  Note: uses add-element-to-lists to attach an element to the
;;   beginning of lists produces in call to generate-permutations
;;   (sort of a recursive call).
;;

(define (use-each-element-as-start-helper done remaining)
  (cond
   ;; if remaining is empty we don't need to do anything
   [(empty? remaining) empty]
   [else
	;; combine the lists produced by generating all permutations
	;; that start with (first remaining), with the lists produced
	;; that start with everything else.
	(append
	 (add-element-to-lists
	  (first remaining)
	  (generate-permutations
	   (append done (rest remaining))))
	 (use-each-element-as-start-helper
	  (append done (list (first remaining)))
	  (rest remaining)))]))
  
;;(generate-permutations '(1 2 3))

;;
;; traveling salesman problem
;;
;; this is a straight-forward (brute force and kinda dumb) approach.
;; the code unnecessarily evaluates lots of duplicates along the way.
;; for example, it finds the cost of tour '(0 1 2 ... n) and the cost
;; of tour (1 2 ... n 0) which are actually the same cost.

(define (select n alist)
  (cond
   [(= 0 n) (first alist)]
   [else
	(select (- n 1) (rest alist))]))

;; tour-distance consumes a list (tour) and
;;   returns a number (cost). Evaluates the tour
;;   by first appending the first city to the end 
;;   (to complete the tour) and then asking the helper
;;   function to add up the costs between adjacent cities.
;;  
;; For example, if given the tour '(1 0 2), the actual cost 
;;   needs to include the cost from city 2 back to city 1.
;; so the list '(1 0 2 1) is sent to the helper function which
;; sums up the costs from 1 to 0, 0 to 2 and 2 to 1
(define (tour-distance tour)
  ;; need sum of consecutive elements of tour
  (tour-distance-helper
   (append tour (cons (first tour) empty))))


;; helper function for evaluating a tour. This function
;; adds the costs for adjacent cities in the tour. 
(define (tour-distance-helper tour)
  (cond
   [ (empty? (rest tour)) 0]
   [else
	(+ (distance cities (first tour) (first (rest tour)))
	   (tour-distance-helper (rest tour)))]))

;; returns the distance (cost) between cities c1 and c2
;; cities is the cost matrix (a list of lists of numbers)
;;  c1 and c2 are integers (city numbers)
(define (distance cities c1 c2)
  (select c1 (select c2 cities)))

;;
;; tsp recursively evaluates each tour, and keeps track of the best one found so far.
;; returns a list that contains the minimum cost found as the first element, then
;; the actual tour
(define (tsp-helper tours best)
  (cond 
   [(empty? tours)  best]
   [else
	(cond
	 [(> (first best) (tour-distance (first tours)))
	  (tsp-helper (rest tours) 
		   (cons (tour-distance (first tours))
				 (first tours)))]
	 [else
	  (tsp-helper (rest tours) best)])]))
 
;;
;; generate a list of integers from 0 to n-1
;;
(define (numbers_to_n n)
  (cond 
    [(= n 0) empty]
    [else
     (append (numbers_to_n (- n 1)) (list (- n 1)))]))


;; tsp int -> list
;; (tsp ncities) finds the tour with the smallest cost
;;   among ncities cities (size is an integer indicating the
;;   number of cities). The costs are stored in the list
;;   cities.
;; 
;;   first creates a list of numbers from 0 to ncities-1,
;;   then gives this list to generate-permuatations, which
;;    returns a list of all possible tours. 
;;    The list of all tours is passed to tsp-helper along with
;;    the initial cost minimum of 1000000 (assumed to be greater than
;;    the actual minimum cost)
(define (tsp ncities)
  (tsp-helper (generate-permutations (numbers_to_n ncities)) '(1000000)))

;; 4 city problem
(define cities4 '(
(  0 10 20  3)
( 10  0  5  8)
( 20  5  0  1)
(  3  8  1  0)))
  

;; 5 city problem
(define cities5 '(
(  0 10 11 10  9)
( 10  0 11  9 12)
( 11 11  0 11 11)
( 10  9 11  0  5)
(  9 12 11  5  0)))
                  


;; 6 city problem
(define cities6 '(
(  0  3 10  5  6 10)
(  3  0  5  3 11  6)
( 10  5  0  8  5  5)
(  5  3  8  0  7  6)
(  6 11  5  7  0 12)
( 10  6  5  6 12  0)
))
                  
	  
;; 7 city problem
(define cities7 '(
(  0  4  9  3  6  9 11)
(  4  0 10 12  7 12 11)
(  9 10  0  7  6  4 12)
(  3 12  7  0 10  6  4)
(  6  7  6 10  0  7 12)
(  9 12  4  6  7  0  7)
( 11 11 12  4 12  7  0)
))
  

		 

;; 8 city problem

(define cities8 '(
(  0   7   5   8   5  10   5   3 )
(  7   0  10  12   9  12   3   8 )
(  5  10   0   5   8   5   6  12 )
(  8  12   5   0  12   8   4   8 )
(  5   9   8  12   0   7   8   4 )
( 10  12   5   8   7   0   8   3 )
(  5   3   6   4   8   8   0   4 )
(  3   8  12   8   4   3   4   0 )
))
  
  
;; test code for the cost matricies shown above
;(define cities cities4)
;(tsp 4)
  
; (define cities cities5)
; (tsp 5)

; (define cities cities6)
; (tsp 6)
  
; (define cities cities7)
; (tsp 7)
  
; (define cities cities8)
; (tsp 8)