Page 2 of 2

Re: Choose numbers at random

Posted: Sun Dec 07, 2008 9:14 pm
by qbg
Paul Donnelly wrote: 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.

Re: Choose numbers at random

Posted: Mon Dec 08, 2008 12:20 am
by Paul Donnelly
qbg wrote:
Paul Donnelly wrote: 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.

Re: Choose numbers at random

Posted: Mon Dec 08, 2008 6:41 am
by dmitry_vk
qbg wrote:
Paul Donnelly wrote: 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.

Re: Choose numbers at random

Posted: Mon Dec 08, 2008 7:41 am
by qbg
dmitry_vk wrote:
qbg wrote:
Paul Donnelly wrote: 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.

Re: Choose numbers at random

Posted: Fri Dec 19, 2008 11:38 am
by jockc
dmitry_vk wrote:
qbg wrote: 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))