On Sep 26, 2:12 pm, Paul Richards <[email protected]> wrote:
> Hi,
> How can I efficiently pick a random element from a sorted-set?
>
I've come up with a bit of a hack, which relies on me not caring about
non-uniform distributions. If I create a custom comparator with a
"random" backdoor, I can select random elements from the sorted set:
(defn my-comp [a b]
(if (or (= :random a) (= :random b))
(- (* 2 (rand-int 2)) 1)
(compare a b)))
; Create test collection (of strings) using the special comparator
(def coll (apply sorted-set-by my-comp (map str (range 1 1000))))
(map #(first (subseq coll > %)) ["500" "200" "700" :random :random])
; Result: ("501" "201" "701" "626" "286")
Bonus question.. What is the distribution of the random selection?
(I suspect elements will be chosen with some probability like (1/2)^H
(where H is the height of the element within the red-black tree). I
should probably generate a histogram to find out..)
--
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
