Choosing randomly between equals
25th May 2020
Suppose you have a list of things ranked according to an integer score:
(defvar *data* '((3 . "one") (3 . "two") (5 . "three") (4 . "four") (4 . "five") (3 . "six") (5 . "seven") (5 . "eight") (4 . "nine") (3 . "ten")))
Just to test the idea I'm using the English words from one to ten, and the score is the length of each word.
If you want to choose the best item you could do something like:
(defun best (alist)
(let ((best (first alist)))
(map nil
#'(lambda (x)
(when (> (car x) (car best)) (setq best x)))
alist)
best))
This gives:
> (best *data*) (5 . "three")
But why return "three" just because it's the first item in the list – what about "seven" and "eight", which have the same score?
In some applications this wouldn't matter, but in a game you might want to randomly choose between three equally good moves, to make the computer play slightly differently each time. What would be the most efficient way of doing this?
Randomise the starting list
One way would be to randomise the order of the starting list. Here's a routine to do it:
(defun random-order (list)
(let ((rlist (map 'list
#'(lambda (item) (cons item (random most-positive-fixnum)))
list)))
(map 'list #'car (sort rlist #'< :key #'cdr))))
So now we can do:
> (best (random-order *data*)) (5 . "eight") > (best (random-order *data*)) (5 . "seven")
But there's a much more efficient way.
Counting repetitions
We use a counter to count the number of repetitions of the best item that we've seen so far:
(defun best-random (alist)
(let ((best (first alist))
(count 0))
(map nil
#'(lambda (x)
(cond
((> (cdr x) (cdr best))
(setq best x count 1))
((= (cdr x) (cdr best))
(incf count)
(when (zerop (random count)) (setq best x)))))
alist)
best))
When we encounter the nth item with the best score found so far, we discard the previous best and choose it in preference with a probability of 1/n.
If we find a better item we reset the counter to 1 and start again.
It took me a bit of time to convince myself that this really does do what we want, namely to randomly choose each of the top-scoring items with equal probability.
Trying it out:
> (best-random *data*) (5 . "eight") > (best-random *data*) (5 . "three")
blog comments powered by Disqus