you're reading...

A Weighted Roulette Wheel in Clojure

In combinatorial experiments that involved generating objects at random with a non-uniform distribution I often see the problem of “Weighted Roulette Wheel”. This model is used for example, in preferential attachment in networks and in dynamic simulations involving preferential movements.

Rich Hickey has made available an ant colony simulation in Clojure. In that program he has a function wrand that does the trick:

(defn wrand 
  "Given a vector of slice sizes, returns the index of a slice given a
  random spin of a roulette wheel with compartments proportional to
  (let [total (reduce + slices)
        r (rand total)]
    (loop [i 0 sum 0]
      (if (< r (+ (slices i) sum))
        (recur (inc i) (+ (slices i) sum))))))

In my articles on generating random graphs:
I have written the following Weighted Roulette Wheel in Clojure, which is called select and is more functional than wrand in that it uses the scan function, and does not rely on procedural (loop (recur)) form.

(defn select [prob]
  (let [keys  (vec (for [[k v] prob] k))
        vals  (for [[k v] prob] v)
        scan  (reductions + vals)
        y     (rand)
        tlist (map (fn[x] (< x y)) scan)
        indxfn (fn ct [lst] (cond (empty? lst) 0
                                    (= (first lst) false) 0
                                    :else (inc (ct (rest lst)))))
        indx (indxfn tlist)]
        (keys indx)))


No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: