;; 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)