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
On Mon, Apr 5, 2010 at 10:19 AM, Lee Spector <[email protected]> wrote:
>
> 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
>
> On Apr 4, 2010, at 11:01 PM, Per Vognsen wrote:
>
>> 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
>>
>> On Mon, Apr 5, 2010 at 3:14 AM, Linus Ericsson
>> <[email protected]> wrote:
>>> 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
>>>
>>> --
>>> You received this message because you are subscribed to the Google
>>> Groups "Clojure" group.
>>> To post to this group, send email to [email protected]
>>> Note that posts from new members are moderated - please be patient with your
>>> first post.
>>> To unsubscribe from this group, send email to
>>> [email protected]
>>> For more options, visit this group at
>>> http://groups.google.com/group/clojure?hl=en
>>
>> --
>> You received this message because you are subscribed to the Google
>> Groups "Clojure" group.
>> To post to this group, send email to [email protected]
>> Note that posts from new members are moderated - please be patient with your
>> first post.
>> To unsubscribe from this group, send email to
>> [email protected]
>> For more options, visit this group at
>> http://groups.google.com/group/clojure?hl=en
>>
>> To unsubscribe, reply using "remove me" as the subject.
>
> --
> Lee Spector, Professor of Computer Science
> School of Cognitive Science, Hampshire College
> 893 West Street, Amherst, MA 01002-3359
> [email protected], 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/
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to [email protected]
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> [email protected]
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
