Christian Marks

This clojure function counts the number of bits in the base 2 representation of a nonnegative integer.

(defn bit-count [n] (loop [i 0 n n] (if (zero? n) i (recur (inc i) (bit-and n (dec n)))))

Here’s a suggestion from the Clojure group to use reduce instead of loop and recur in the calculation of the order of a permutation. The reduce form saves a variable at the expense of some time. The function (cycle-leader? perm i) returns true if and only if i is the least element of the unique cycle containing i in perm. The predicate form improves readability at the expense of introducing a test.

(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))

A further reduction with reduce is possible by combining the test for a cycle leader with the cycle count.

(defn cycle-leader-length [perm i]
    (loop [cycle 1  j (nth perm i)]
        (cond (< j i) 1
              (= j i) cycle      
              :else (recur (inc cycle) (nth perm j)))))

(defn order-perm [perm] 
    (reduce (fn [order i] (math/lcm (cycle-leader-length perm i) order))  1 perm))

This is the most compact so far, but the original code with fewer tests and cycle length computations is faster.