Commits

Robert Smith committed 7815ecb

Allow arbitrary discrete distributions when choosing a random element.

Comments (0)

Files changed (1)

 (defun random-elt (seq &optional distribution)
   "Choose a random element of SEQ according to DISTRIBUTION. If
 DISTRIBUTION is null, the distribution will be uniform. Otherwise,
-<stub>."
+DISTRIBUTION should be a list of probability values"
   (if (null distribution)
       (elt seq (random-between 0 (1- (length seq))))
-      (stub 'random-elt)))
+      (let* ((cum (loop :for x :in distribution
+                        :sum x :into s
+                        :collect s))
+             (r (random 1.0d0))
+             (pos (position-if (lambda (x) (<= r x)) cum)))
+        (if (or (null pos)
+                (>= pos (length seq)))
+            (error "Bad distribution: ~S" distribution)
+            (elt seq pos)))))
 
 (defun nshuffle-vector (vector)
   "Destructively shuffle VECTOR randomly."