I implemented the "Flavius Josephus" algorithm from Programming Praxis
in Clojure using loop/recur. My first version looked like this:
(defn rotate-left
([ln n m]
(take n (drop (dec m) (cycle ln))))
([ln m] (rotate-left ln (count ln) m)))
(defn josephus3 [N M] ;; execute every mth soldier
(loop [soldiers (range N)
m M
deceased '()]
(let [n (count soldiers)]
(cond
(zero? n) deceased
true (let [r (rotate-left soldiers n m)
dead (cons (first r) deceased)
survivors (rest r)]
(recur survivors m dead))))))
This works fine, but I don't really need to count the soldiers every
pass, it always decreases by 1. So I wrote this version in which n is
one of the loop parameters:
(defn josephus4 [N M] ;; execute every mth soldier
(loop [soldiers (range N)
n N
m M
deceased '()]
(cond
(zero? n) deceased
true (let [r (rotate-left soldiers n m)
dead (cons (first r) deceased)
survivors (rest r)]
(recur survivors (dec n) m dead)))))
Both work for small N (e.g. 41) but the second one fails for large
(41000) N with a stack overflow.
What am I missing here?
Thanks,
Charles
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to clojure@googlegroups.com
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
clojure+unsubscr...@googlegroups.com
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
