The following code snippets provide a means of solving the traveling salesman problem in the clojure programming language.

Don’t know what it is? Look here: traveling salesman

The code (currently heavily lacks comments, will do some in time):

; we use permute to find the x-th permutation of a list, a, in lexicographic order.
(defn permute [x a]
(if (= (count a) 1 ) a
(letfn [(fact [num] (if (< num 2) 1 (* num (fact (- num 1)))))]
(let [p (mod(/ x (fact (- (count a) 1))) (count a))]
(vec(cons (nth a p)(permute (mod x (fact (- (count a) 1))) (vec (concat (subvec a 0 p) (subvec a (inc p) (count a)))))))))))

; figure out the possible routes with routes()
; n is the start point
; i.e. (routes 0, [1 2 3 4]) gives all routes starting with 1
; starting from [1 2 3 4] in the order.
(defn routes [n, myList] (if (< n (/(factorial (count myList)) (count myList)))
(vec(cons (permute n myList) (routes (inc n) myList)))))

;list out the distances – this is for testing purposes.
(def dists [[0,21,41,30,43],[21,0,21,19,24],[41,21,0,20,20],[30,19,20,0,36],[43,24,20,36,0]])

; this is a helper factorial function
(defn factorial [n] (if (< n 2) 1 (* n (factorial (dec n)))))

; calculate the distance
(defn distance [route]
;finished going through route, figure out distance to the start
(if (= (count route) 1) (nth (nth dists (first route)) 0)
;get the first and second portions of the route
(let [f (first route), s (first(rest route))]
;keep total using distances [f][s]
;recur with (rest route)
;(println (nth (nth dists f)s))
(+ (nth (nth dists f) s) (distance (rest route))))))

;iterate through routes find the shortest distance, and return the route.

(defn find-best [toCheck best dist]
(if (= (count toCheck) 0) [dist, best]
(if (< (distance (first toCheck)) dist)
;then
(find-best (rest toCheck) (first toCheck) (distance (first toCheck)))
;else
(find-best (rest toCheck) best dist))))

;the test – define a list of routes
(def route-list(routes 0 [0 1 2 3 4]))

; find the best one via brute force.
(find-best (rest route-list)(first route-list)(distance (first route-list)))

the end result of my test:

[115, [0 1 4 2 3]].
Checked. It was right. Others were equal in distance, but still.
It was right.

Spent all day on this.

Mind = blown.