Created
April 17, 2020 18:15
-
-
Save emdeesee/4e54fb98606fdf691674cd0db39c36ab to your computer and use it in GitHub Desktop.
Weighted random selection in elisp
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; 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 | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment