On Jul 10, 10:16 pm, FL <[email protected]> wrote:
\> .... If you replace your
.......
> > (defn order-perm [perm]
> > (let [n (count perm)]
.......
> with the more compact
>
> (defn order-permo [perm]
> (reduce (fn [order i] (if (= i (next-cycle-leader perm i))
> (math/lcm (cycle-length perm i)
> order)
> order))
> 1 perm))
>
> you'll be rewarded with better performance with permutations of size
> <= 100000,
Thank you. Based on this I've simplified the code further.
The (new) predicate (cycle-leader? perm i) is true if and only if
i is the least element of the unique cycle containing i
in the permutation perm. This is more readable, though the
extra test compared with the original adds to execution time.
(ns knuth
(:require [clojure.contrib.math :as math]))
(defn random-perm [n] (shuffle (range n)))
(defn cycle-leader? [perm i]
(loop [j (nth perm i)]
(cond (< j i) false
(= j i) true
:else (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]
(reduce
(fn [order i] (if (cycle-leader? perm i)
(math/lcm (cycle-length perm i) order)
order))
1 perm))
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
