Christian Marks

The non-functional style of the code of the previous post goes against the spirit of Clojure. The code below is a translation into Clojure of the code to compute the order of a (random) permutation from previous posts. By comparison with Common Lisp, construction of random permutations is considerably simplified in Clojure, which like Python provides a random shuffle function.

The function order-perm below is an adaptation of the constant space algorithm of C. J. Gower, from page 4 of Knuth, D. E., “Selected Papers on Analysis of Algorithms,” CSLI Lecture Notes Number 102, CSLI Publications, (2000). The order of a permutation is the least common multiple of its cycle lengths; the function order-perm makes use of the associativity of the least common multiple. The function (next-cycle-leader perm i) locates the first index of the cycle of the permutation perm at or below index i, as i ranges over the permutation indices in order. If the function (next-cycle-leader perm i) returns i itself, then i is the least index of the cycle containing index i (in index order, by induction). That accounts for the if form in the recur function of order-perm: if the index i is the least index of the cycle containing it, the binding of order in the loop form is updated with the least common multiple of the length of the cycle at index i and the current value of order, which is the least common multiple of the cycles visited so far, in order of cycle leader index; otherwise the binding of order is unchanged.

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

A test in the read-eval-print loop:

knuth=> (order-perm [9 1 6 0 3 2 5 4 8 7])
15
knuth=> (order-perm [6 3 4 7 0 5 2 1 8 9])
12
knuth=> (order-perm [8 0 1 5 2 9 7 4 6 3])
21

The running time compares favorably with common lisp, though I ran out of heap space in the Java Virtual Machine:

user=> (load "knuth")                        
nil
user=> (ns knuth)                            
nil
knuth=> (time (order-perm (random-perm 100000)))
"Elapsed time: 360.895 msecs"
1065606748036679276883000
knuth=> (time (order-perm (random-perm 1000000)))
"Elapsed time: 5584.238 msecs"
753574706077650707341441647806967057600
knuth=> (time (order-perm (random-perm 10000000)))
java.lang.OutOfMemoryError: Java heap space (NO_SOURCE_FILE:0)