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 slices." [slices] (let [total (reduce + slices) r (rand total)] (loop [i 0 sum 0] (if (< r (+ (slices i) sum)) i (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)))