The clojure code below applies the constant space algorithm to apply a
permutation to an array of C. J. Gower to the computation of the order
of a permutation [Knuth, D. E., “Selected Papers on Analysis of
Algorithms,” CSLI Lecture Notes Number 102, CSLI Publications, (2000),
p 4]. The order of a permutation is the least common multiple of its
cycle lengths; the function order-perm below makes use of the
associativity of the least common multiple.
I'm using recur, however some clojure programmers inform me that recur
"should" be eliminated in favor of doseq or fold. I see nothing wrong
with recur myself--am I missing
something?
(ns knuth
(:require [clojure.contrib.math :as math]))
(defn random-perm [n] (shuffle (range n)))
(defn next-cycle-leader [perm i]
(loop [j (nth perm i)]
(if (<= j i)
j
(recur (nth perm j)))))
(defn cycle-length [perm i]
(loop [cycle 1 j (nth perm i)]
(if (= i j)
cycle
(recur (inc cycle) (nth perm j)))))
(defn order-perm [perm]
(let [n (count perm)]
(loop [i 0 order 1]
(if (= i n)
order
(recur (inc i)
(if (= i (next-cycle-leader perm i))
(math/lcm (cycle-length
perm i) order)
order))))))
--
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
