Choose numbers at random

Wazzaaaaaa! I'm trying to create two different functions that choose numbers at random.

I want something like this: (ranged-random 1 10)

RANGED-RANDOM would simply pick a number given the range (inclusively)

I also want something like this: (list-random '(6 8 15 90 3 5))

LIST-RANDOM would pick one of the numbers in the list at random.

Are there any functions like these already, or will I have to make them myself?

There isn't anything built-in.

For the former, you could do something like

(+ low (random (1+ (- high low))))

For the latter, one option is

(elt list (random (length list)))

Excellent!

The function for the range is clever, I would have been banging my head for hours on that one.

As for the second function, I should have paid closer attention in PCL when it talks about sequences and vectors. I was searching the Hyperspec for stuff related to numbers, when I should have been looking at sequences -_-

This will be most helpful. Thank you my nerd brother!

mijokijo wrote:Excellent!

The function for the range is clever, I would have been banging my head for hours on that one.

As for the second function, I should have paid closer attention in PCL when it talks about sequences and vectors. I was searching the Hyperspec for stuff related to numbers, when I should have been looking at sequences -_-

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.

'Eeeeeeyyyyy!

While it probably will be fine for my purpose, if ever it should seem slower than it should be, tell me what a good alternative to storing the values in a list would be? Hash tables?

mijokijo wrote:'Eeeeeeyyyyy!

While it probably will be fine for my purpose, if ever it should seem slower than it should be, tell me what a good alternative to storing the values in a list would be? Hash tables?

If you wanted to quickly pick random items from a set of numbers, a vector might be the natural choice. Getting the length of a list requires traversing it to the end, and getting the nth element from a list requires another traversal to the element you want. A vector stores its size and elements can be looked up directly, so if you were to frequently pick random elements from a sequence, a vector might be a better choice. Xach's code will work on vectors too, if you feed it one.

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:

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

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:

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.

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

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.

If it's any consolation, I took "that one" to mean "that solution" and not "Keep in mind that: one will have to...".

Wodin wrote:If it's any consolation, I took "that one" to mean "that solution" and not "Keep in mind that: one will have to...".

It is.

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

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:

(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 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:

(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:

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.

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:

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:

(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))