Can I make a Deterministic Shuffle in clojure?

Question

I'd like to make some shuffles of sets which will be the same every time my program is run:

This is one way to do it:

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(defn colour-shuffle [n] 
  (let [cs (nth (clojure.math.combinatorics/permutations colours) n)]
    [(first cs) (drop 1 cs)]))

; use (rand-int 40320) to make up numbers, then hard code:
(def colour-shuffle-39038 (colour-shuffle 39038))
(def colour-shuffle-28193 (colour-shuffle 28193))
(def colour-shuffle-5667  (colour-shuffle 5667))
(def colour-shuffle-8194  (colour-shuffle 8194))
(def colour-shuffle-13895 (colour-shuffle 13895))
(def colour-shuffle-2345  (colour-shuffle 2345))

colour-shuffle-39038 ; ["white" ("magenta" "blue" "green" "cyan" "yellow" "red" "black")]

But it takes a while to evaluate, and seems wasteful and rather inelegant.

Is there some way of generating shuffle 39038 directly, without generating and consuming all of the sequence?

(I already realise that I can hard code them, or bring the effort back to compile time with a macro. That also seems a bit rubbish.)

Answer 1

Sounds like you want to number permutations:

(def factorial (reductions * 1 (drop 1 (range))))

(defn factoradic [n] {:pre [(>= n 0)]}
   (loop [a (list 0) n n p 2]
      (if (zero? n) a (recur (conj a (mod n p)) (quot n p) (inc p)))))

(defn nth-permutation [s n] {:pre [(< n (nth factorial (count s)))]}
  (let [d (factoradic n)
        choices (concat (repeat (- (count s) (count d)) 0) d)]
    ((reduce 
        (fn [m i] 
          (let [[left [item & right]] (split-at i (m :rem))]
            (assoc m :rem (concat left right) 
                     :acc (conj (m :acc) item))))
      {:rem s :acc []} choices) :acc)))

Let's try it:

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(nth-permutation colours 39038)
=> ["white" "magenta" "blue" "green" "cyan" "yellow" "red" "black"]

...as in the question, but without generating any of the other permutations.

Well enough, but would we get them all?

(def x (map (partial nth-permutation colours) (range (nth factorial (count colours)))))

(count x)
=> 40320
(count (distinct x))
=> 40320
(nth factorial (count colours))
=> 40320

Note the permutations are generated in (lexicographic by index) order:

user=> (pprint (take 24 x))
(["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"]
 ["red" "blue" "green" "yellow" "cyan" "magenta" "white" "black"]
 ["red" "blue" "green" "yellow" "cyan" "black" "magenta" "white"]
 ["red" "blue" "green" "yellow" "cyan" "black" "white" "magenta"]
 ["red" "blue" "green" "yellow" "cyan" "white" "magenta" "black"]
 ["red" "blue" "green" "yellow" "cyan" "white" "black" "magenta"]
 ["red" "blue" "green" "yellow" "magenta" "cyan" "black" "white"]
 ["red" "blue" "green" "yellow" "magenta" "cyan" "white" "black"]
 ["red" "blue" "green" "yellow" "magenta" "black" "cyan" "white"]
 ["red" "blue" "green" "yellow" "magenta" "black" "white" "cyan"]
 ["red" "blue" "green" "yellow" "magenta" "white" "cyan" "black"]
 ["red" "blue" "green" "yellow" "magenta" "white" "black" "cyan"]
 ["red" "blue" "green" "yellow" "black" "cyan" "magenta" "white"]
 ["red" "blue" "green" "yellow" "black" "cyan" "white" "magenta"]
 ["red" "blue" "green" "yellow" "black" "magenta" "cyan" "white"]
 ["red" "blue" "green" "yellow" "black" "magenta" "white" "cyan"]
 ["red" "blue" "green" "yellow" "black" "white" "cyan" "magenta"]
 ["red" "blue" "green" "yellow" "black" "white" "magenta" "cyan"]
 ["red" "blue" "green" "yellow" "white" "cyan" "magenta" "black"]
 ["red" "blue" "green" "yellow" "white" "cyan" "black" "magenta"]
 ["red" "blue" "green" "yellow" "white" "magenta" "cyan" "black"]
 ["red" "blue" "green" "yellow" "white" "magenta" "black" "cyan"]
 ["red" "blue" "green" "yellow" "white" "black" "cyan" "magenta"]
 ["red" "blue" "green" "yellow" "white" "black" "magenta" "cyan"])

Answer 2

clojure.core/shuffle uses java.util.Collection/shuffle, which takes an optional random number generator. clojure.core/shuffle does not use this argument, but you could use it to create a variation of shuffle that takes an additional seed value argument, and use that seed value to create a random number generator to pass to java.util.Collection/shuffle:

(defn deterministic-shuffle
  [^java.util.Collection coll seed]
  (let [al (java.util.ArrayList. coll)
        rng (java.util.Random. seed)]
    (java.util.Collections/shuffle al rng)
    (clojure.lang.RT/vector (.toArray al))))

Answer 3

My recommendation: use a closure and calculate the permutations only once. Then re-use those permutations to select an element from it. In your function colour-shuffle, the permutations are re-calculated for every call which isn't very efficient.

(use 'clojure.math.combinatorics)

(def colours ["red" "blue" "green" "yellow" "cyan" "magenta" "black" "white"])

(def select-permutation
  (let [perms (permutations colours)]
    (fn [n]
      (nth perms n))))

(defn colour-shuffle [n] 
  (let [cs (nth (permutations colours) n)]
    [(first cs) (drop 1 cs)]))

(time (do  (def colour-shuffle-39038 (colour-shuffle 39038))
           (def colour-shuffle-28193 (colour-shuffle 28193))
           (def colour-shuffle-5667  (colour-shuffle 5667))
           (def colour-shuffle-8194  (colour-shuffle 8194))
           (def colour-shuffle-13895 (colour-shuffle 13895))
           (def colour-shuffle-2345  (colour-shuffle 2345))))

(time (do (def select-permutation-39038 (select-permutation 39038))
          (def select-permutation-28193 (select-permutation 28193))
          (def select-permutation-5667  (select-permutation 5667))
          (def select-permutation-8194  (select-permutation 8194))
          (def select-permutation-13895 (select-permutation 13895))
          (def select-permutation-2345  (select-permutation 2345))))

(time (do  (def colour-shuffle-39038 (colour-shuffle 39038))
           (def colour-shuffle-28193 (colour-shuffle 28193))
           (def colour-shuffle-5667  (colour-shuffle 5667))
           (def colour-shuffle-8194  (colour-shuffle 8194))
           (def colour-shuffle-13895 (colour-shuffle 13895))
           (def colour-shuffle-2345  (colour-shuffle 2345))))

(time (do (def select-permutation-39038 (select-permutation 39038))
          (def select-permutation-28193 (select-permutation 28193))
          (def select-permutation-5667  (select-permutation 5667))
          (def select-permutation-8194  (select-permutation 8194))
          (def select-permutation-13895 (select-permutation 13895))
          (def select-permutation-2345  (select-permutation 2345))))

Output:

"Elapsed time: 129.023 msecs"
"Elapsed time: 65.472 msecs"
"Elapsed time: 182.226 msecs"
"Elapsed time: 5.715 msecs"

Note that the second run of time using select-permutation is even faster. This is because results of lazy sequences are cached after calculation. Requesting an element very deep into the lazy-seq will cause all preceding elements to be calculated as well. This is why the first run takes much longer. When requesting the 39039th element from a fresh lazy-seq will cause at least 39040 elements to be calculated (in chucks of 32).

Btw, If your random numbers are going to be hardcoded anyway, you might as well hardcode the above retrieved permutations.