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

Thanhthank

You could use a standard shuffle algorithm like Fisher–Yates but add a seed argument for the RNG – Revivalist

Mike, yes, that's what I was thinking. Is there one already in clojure or one of its libs or do I have to code one up? – Thanhthank

Sounds like you are asking if you can number permutations and choose the nth one without generating the n-1 before it. Yes, you do this by implementing a decoding of Lehmer codes. I've taken a stab at this in my answer. – Cascara

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"])

Cascara

Dude, that is the sweetest thing ever. If you change the 1 in factorial to 1N then you can do (nth-permutation (range 30) 100000000000000000000000) ;-> [0 1 2 3 4 5 9 26 29 13 10 18 28 16 15 8 27 20 25 23 19 14 21 22 24 7 12 17 6 11] in very little time indeed. Exactly what I wanted and beautifully done. Thank you so much. Do you mind if I blog about it? (learningclojure.com) – Thanhthank

@JohnLawrenceAspden Feel free to use in any way you like! – Cascara

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

Lecythus

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.

Goodly

Don't forget about ...every time my program is run... part. – Haematothermal

If you pick the same "random" elements (permutations) every time the program is run, you might as well just hard-code those elements. See the last line in my answer. – Goodly