Reorder a list randomly?

[Linus Ericsson]

Hello Clojure!

Is there any straight-forward way to randomly reorder a list?

ie:

(randomize-list (list 1 2 3 4))
-> (3 2 1 4)

Regards,
Linus Ericsson

[Lee Spector]

There's a shuffle function in seq-utils:

user=> (use 'clojure.contrib.seq-utils)
nil
user=> (shuffle (list 1 2 3 4))
(3 4 1 2)

-Lee

> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to clo...@googlegroups.com
> Note that posts from new members are moderated - please be patient with your first post.
> To unsubscribe from this group, send email to
> clojure+u...@googlegroups.com
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en

--
Lee Spector, Professor of Computer Science
School of Cognitive Science, Hampshire College
893 West Street, Amherst, MA 01002-3359
lspe...@hampshire.edu, http://hampshire.edu/lspector/
Phone: 413-559-5352, Fax: 413-559-5438

Check out Genetic Programming and Evolvable Machines:
http://www.springer.com/10710 - http://gpemjournal.blogspot.com/

[Per Vognsen]

The seq-utils library has a shuffle function that calls out to
java.util.Collections.

If you want to do it yourself, the easiest would be

(defn naive-shuffle [xs]
(let [v (vec xs)]
(->> (count v) range lex-permutations rand-elt (map v))))

This uses the seq-utils and combinatorics libraries from clojure.contrib.

However, generating all permutations obviously doesn't scale beyond a
couple of elements. For that you will need a real algorithm like the
Knuth shuffle:

(defn swap-elts [x i j]
(assoc x i (x j) j (x i)))

(defn rand-range
([n] (rand-int n))
([m n] (+ m (rand-int (- n m)))))

(defn knuth-shuffle [xs]
(let [v (vec xs)]
(reduce #(swap-elts %1 %2 (rand-range %2 (count %1))) v (range (count v)))))

-Per

[Lee Spector]

Since we're having a shuffle-a-thon, here's a version I wrote that I kind of like for its simplicity, even though it uses a recursive call that Clojure apparently can't optimize. (FWIW I wrote a version that used loop/recur instead, but it was actually slower for some reason):

(defn shuffle
[lst]
(if (empty? (rest lst))
lst
(let [index (rand-int (count lst))
item (nth lst index)
remainder (concat (subvec (into [] lst) 0 index)
(subvec (into [] lst) (inc index)))]
(cons item (shuffle remainder)))))

-Lee

> To unsubscribe, reply using "remove me" as the subject.

[Per Vognsen]

A quick test shows that it's about 3 times faster than my
knuth-shuffle. Here's a version using transients that is 2x faster but
still not quite as fast as yours:

(defn rand-range [m n]

(+ m (rand-int (- n m))))

(defn swap-entries! [x i j]
(assoc! x i (x j) j (x i)))

(defn knuth-shuffle [xs]
(let [v (transient (vec xs)), n (count v)]
(persistent! (reduce #(swap-entries! %1 %2 (rand-range %2 n)) v
(range n)))))

-Per

[Mark Engelberg]

On my system, knuth-shuffle performs several times faster than Spector's recursive functional shuffle on smallish lists, and the difference grows even more dramatic as the list grows, which is what I'd expect (since knuth-shuffle is O(n) and shuffle is O(n^2)).

[Per Vognsen]

Wow, you're right. The partial laziness of his code was foiling my benchmark.

-Per

[Lee Spector]

Ah -- maybe that foiled my timings too. I didn't expect it to be fast -- just clear (at least to this Lisp programmer).

-Lee

[Per Vognsen]

On Mon, Apr 5, 2010 at 11:33 AM, Lee Spector <lspe...@hampshire.edu> wrote:
>
> Ah -- maybe that foiled my timings too. I didn't expect it to be fast -- just clear (at least to this Lisp programmer).

Embrace recursion combinators! They are warm and fuzzy!

Here's a gist of the final cleaned up version of my code. The code
itself is only three lines; the rest consists of very general purpose
utilities that I find myself using again and again.

http://gist.github.com/356035

-Per

[Sean Devlin]

If this is significantly faster than c.c.seq/shuffle, you should
submit a patch. I know Rich was complaining about the speed of that
fn in the past.

Also, I'd reverse the arg order of with-transient. I think

(with-transient f x)

reads easier. Also, it should probably end with a bang, because I
don't think it's safe in the STM.

Great work guys.

Sean

On Apr 5, 12:52 am, Per Vognsen <per.vogn...@gmail.com> wrote:

> > lspec...@hampshire.edu,http://hampshire.edu/lspector/

> > Phone: 413-559-5352, Fax: 413-559-5438
>
> > Check out Genetic Programming and Evolvable Machines:

> >http://www.springer.com/10710-http://gpemjournal.blogspot.com/

[Per Vognsen]

In my experiments my code is still about 1.5x slower than
seq-utils.shuffle. The current implementation of seq-utils.shuffle
simply converts to an ArrayList, calls java.util.Collections.shuffle,
and converts back to a Clojure sequence. Here's a quick experiment:

user> (def v (vec (range 500000)))
#'user/v
user> (time (do (doall (shuffle v)) nil))
"Elapsed time: 449.001 msecs"
nil
user> (def a (java.util.ArrayList. v))
#'user/array
user> (time (do (java.util.Collections/shuffle a) nil))
"Elapsed time: 102.331 msecs"
nil

Each of those timings were repeated several things to make sure they
were sufficiently stable.

The conclusion is that java.util.Collections.shuffle is plenty fast.
Most of the time (over 3/4ths) taken by seq-utils.shuffle goes into
conversions. But even 450 ms for shuffling a 500,000 element list
isn't too bad. For comparison, the time to sum that many elements with
#(reduce + %) is about 50 ms.

-Per

[Linus Ericsson]

I'm overwhelmed by the answers, thank you all! Now back to the REPL.

/Linus

2010/4/5 Per Vognsen <per.v...@gmail.com>