## Choose numbers at random

Discussion of Common Lisp

### Re: Choose numbers at random

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.
qbg

Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

### Re: Choose numbers at random

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.
Paul Donnelly

Posts: 148
Joined: Wed Jul 30, 2008 11:26 pm

### Re: Choose numbers at random

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.
dmitry_vk

Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan

### Re: Choose numbers at random

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/33/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.
qbg

Posts: 64
Joined: Mon Jun 30, 2008 1:05 pm
Location: Minnesota

### Re: Choose numbers at random

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/33/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))`
jockc

Previous

Return to Common Lisp

### Who is online

Users browsing this forum: No registered users and 4 guests