Choose numbers at random

[qbg]

I suspected someone would be along with a way to do it in one traversal, and I think I meant only that particular implementation when I referred to the necessity of iterating twice. Don't know why I would make a blanket statement like that.

To clarify: I was not implying that that you stated all implementations must iterate two (well, actually somewhere between one and two) times.

Furthermore, your solution is probably better, not only because it is shorter, but because I'd guess that it would be faster (unless calling random and testing for zero is sufficiently fast enough compared to taking a cdr of a cons cell on your implementation). The technique I demonstrated just shows how one can perform this task when you don't know how many elements you are going to get.

[Paul Donnelly]

I suspected someone would be along with a way to do it in one traversal, and I think I meant only that particular implementation when I referred to the necessity of iterating twice. Don't know why I would make a blanket statement like that.

To clarify: I was not implying that that you stated all implementations must iterate two (well, actually somewhere between one and two) times.

Furthermore, your solution is probably better, not only because it is shorter, but because I'd guess that it would be faster (unless calling random and testing for zero is sufficiently fast enough compared to taking a cdr of a cons cell on your implementation). The technique I demonstrated just shows how one can perform this task when you don't know how many elements you are going to get.

And thank you for posting it, I found it interesting.

[dmitry_vk]

Keep in mind, that one will have to iterate over the list twice, once to get its length, and once to get the random element (apologies if you know this already). It's probably fine for your purposes, but if it seems slower than it should be, consider either not using a list or storing the list length somewhere for quick lookup.

You should be able to do it in one traversal, at the cost of more calls to random:

Code: Select all

(defun random-nth (list)
  (let ((element (car list))
    (n 2))
    (dolist (e (cdr list))
      (if (zerop (random n))
        (setf element e))
      (incf n))
    element))


In this solution, choice is random but the probability distribution is not uniform.

[qbg]

Keep in mind, that one will have to iterate over the list twice, once to get its length, and once to get the random element (apologies if you know this already). It's probably fine for your purposes, but if it seems slower than it should be, consider either not using a list or storing the list length somewhere for quick lookup.

You should be able to do it in one traversal, at the cost of more calls to random:

Code: Select all

(defun random-nth (list)
  (let ((element (car list))
    (n 2))
    (dolist (e (cdr list))
      (if (zerop (random n))
        (setf element e))
      (incf n))
    element))


In this solution, choice is random but the probability distribution is not uniform.

It should be. Think about the case of 4 items in a list. A table of probabilities would then be something like:

Code: Select all

1/1 
1/2  1/2 
2/3  2/3  1/3
3/4  3/4  3/4  1/4


First column is for choosing the first one, second for the second, etc. To get the total probability, you multiply all the elements in a column together, and you end up with 1/4 for each column. Note that the reason for it being triangular is that it doesn't matter what was chosen before you reach the number you want to produce.

[jockc]

In this solution, choice is random but the probability distribution is not uniform.

It should be. Think about the case of 4 items in a list. A table of probabilities would then be something like:

Code: Select all

1/1 
1/2  1/2 
2/3  2/3  1/3
3/4  3/4  3/4  1/4


First column is for choosing the first one, second for the second, etc. To get the total probability, you multiply all the elements in a column together, and you end up with 1/4 for each column. Note that the reason for it being triangular is that it doesn't matter what was chosen before you reach the number you want to produce.

Easy to demonstrate:

Code: Select all

(loop with hash = (make-hash-table)
      for count below 100000
      for value = (random-nth '( 1 2 3 4 5 6 7 8 9 10))
      do (incf (gethash value hash 0))
      finally (maphash #'(lambda (k v) (format t "~a -> ~a~%" k v)) hash))