Weighted random selection in elisp

weighted-random.el

;; In this population, a should be selected with frequency of 10%, while
;; b and c are each chosen with frequency 45%.
(defvar weights '(10 45 45))
(defvar population '(a b c))

(defun cumulative-weights (weights)
  "Return the total of `weights' and the cumulative distribution
table."
  (loop for w in weights
        sum w into total
        collect total into cumulative
        finally (return (values total cumulative))))

(defun bisect (list n)
  "Find the index where inserting `n' in the sorted list `list'
would maintain the sort."
  (loop for w in list
        for index = 0 then (1+ index)
        when (> w n) return index
        finally (return index)))

(defun choice (population weights)
  "Randomly choose among `population', where selection preference
is informed by `weights'. For example, with population (A B) and
weight (25 75), A should be chosen 25% of the time while B is
chosen 75%.

Weights need not be percentages; they can be any set of values.
Selections among the population will be made proportionally to
the sum of the weights."
  (when (listp population)
    (assert (= (length population) (length weights)))
    (multiple-value-bind (total cumulative) (cumulative-weights weights)
      (nth
       (bisect cumulative (random total))
       population))))

(loop repeat 100000
      for result = (choice population weights)
      count (eq result 'a) into as
      count (eq result 'b) into bs
      count (eq result 'c) into cs
      finally (return (list 'a as 'b bs 'c cs)))
;; => (a 10019 b 45146 c 44835) for example