Round Robin Tournament Scheduling Algoritme in Clojure

gistfile1.clj

;; Dit programma maakt gebruik van het Round Robin Tournament Scheduling Algoritme
;; Zoals beschreven op http://en.wikipedia.org/wiki/Round-robin_tournament
;; Eerst volgen er wat losse fragmenten Clojure-code om het een en ander toe te lichten
;; De eigenlijke oplossing bestaat uit de functies turn-around en solutions

(def students (shuffle (range 100))) ; students is een lijst van de getallen 0 t/m 99, geshuffeld
(def first-half (take (/ (count students) 2) students)) ; de eerste helft van de lijst studenten
(def second-half (reverse (drop (/ (count students) 2) students))) ; de tweede helft
;;eventueel ook te schrijven met behulp van de threading macro -> als:
(def second-half (-> (count students) (/ 2) (drop students) reverse))

;; de eerste weekindeling volgens het round robin tournament algoritme
;; map neemt een functie en meerdere collecties en past de functie toe op telkens het nde element van de 1ste, 2e, etc collectie
;; vector is een functie die van een variabel argumenten een vector maakt (een soort array)
;; dus (map vector [1 2 3] [4 5 6]) levert op: ( (vector 1 4) (vector 2 5) (vector 5 6) ) => ([1 4] [2 5] [5 6])
(def first-week (map vector first-half second-half)) 

(def new-first-half (butlast (concat [(first first-half)] [(first second-half)] (rest first-half)))) ; de nieuwe bovenste helft volgens rrt
(def new-second-half (concat (rest second-half) [(last first-half)])) ;de nieuwe onderste helft volgens rrt

;; de tweede week op dezelfde manier berekend als de eerste week, maar dan op nieuwe data
(def second-week (map vector new-first-half new-second-half)) 

;; berekening van de nieuwe helften op basis van de oude helften uitgedrukt in een functie
(defn turn-around [first-half second-half]
  [(butlast (concat [(first first-half)] [(first second-half)] (rest first-half)))
   (concat (rest second-half) [(last first-half)])])

;; oplossingen genereren, functie van de studentenlijst en het aantal te genereren weken
;; loopen in clojure is altijd recursief
;; je kunt in de loop een aantal argumenten specificeren met beginwaardes
;; het argument first-half  krijgt dus de beginwaarde "de helft van de studentenlijst", etc
;; op te merken is dat result (vector) als beginwaarde heeft, dat is gewoon een lege vector
;; als n 0 is, dan stopt de loop en worden de resultaten teruggegeven:
;; een vector van lijsten (de weken) van vectoren (de paren)
;; als n niet nul is dan berekenen we de nieuwe bovenste en onderste helft en gaan
;; we een recursieslag in met nieuw berekende argumenten 
(defn solutions [students nweeks]
  (loop [first-half (take (/ (count students) 2) students)
	 second-half (reverse (drop (/ (count students) 2) students))
	 n nweeks
	 result (vector)]
    (if (zero? n) result
	(let [[new-first-half new-second-half] (turn-around first-half second-half)]
	  (recur new-first-half new-second-half (dec n)
		 (conj result (map vector first-half second-half)))))))

(solutions (range 4) 3) ; even een testje om te kijken of het goed gaat
(solutions students 99) ; een oplossing voor 100 studenten, 99 weken
(time (solutions students 99)) ; varieert van 6 tot 12 ms...