Subject: Re: make a list of different random numbers
From: rpw3@rpw3.org (Rob Warnock)
Date: Wed, 18 Feb 2009 05:22:53 -0600
Newsgroups: comp.lang.lisp
Message-ID: <Tt6dnXoBBpIQcgbUnZ2dnUVZ_jmdnZ2d@speakeasy.net>
Marco Antoniotti  <marcoxa@gmail.com> wrote:
+---------------
| "William James" <> wrote:
| > Marco Antoniotti wrote:
| > > On Feb 17, 4:02�pm, david <not...@gmail.com> wrote:
| > > > i would like to get a list of 4 different random numbers.
| > > > (wk wn wb bk)
| > > > i started this code :
| > > > (defun random-position () (1+ (random 64)))
...
| I'll grant you that this is even better than my original one.
| (defun random-pos (&optional (bound 1.0))
|    (loop collect (random bound) into list
|          until (= 4 (length (setf list (delete-duplicates list :test '=))
|          finally (return list))
| a little more verbose, but same thing.  Plus I can compile it.
+---------------

I'm confused [not a rare event!]. I thought the OP wanted a
"random-position", which implies to me values that can be used
as indices in an array, so don't the values have to be integers?
In which case, the BOUND can never be less than the desired
result length. That is, your code works fine for (RANDOM-POS 1.0),
but loops forever on (RANDOM-POS 1) or 2 or 3.

Anyway, whilst pondering that I realized there's a still faster way to do
this than use DELETE-DUPLICATES, especially for *large* result lengths:

    > (defun random-positions (length &optional (bound length))    
	(assert (or (<= length bound) (and (floatp bound) (plusp bound))))
	(let ((ht (make-hash-table :test #'eql)))
	  (loop for key = (random bound)
		while (< (hash-table-count ht) length)
	    do (setf (gethash key ht) nil))
	  (loop for key being the hash-keys of ht collect key))) 

    RANDOM-POSITIONS
    > (compile *)

    RANDOM-POSITIONS
    NIL
    NIL
    > (random-positions 4)

    (1 3 2 0)
    > (random-positions 4)

    (3 2 0 1)
    > (random-positions 20)

    (5 18 12 1 7 15 9 0 19 3 11 14 6 2 10 16 4 8 17 13)
    > (random-positions 20)

    (15 19 12 10 13 8 5 4 18 17 16 0 3 9 11 2 7 14 1 6)
    > (random-positions 6 1.0)

    (0.14457798 0.42955732 0.4225546 0.60270786 0.46022022 0.492818)
    > (random-positions 6 1.0)

    (0.9264666 0.22035849 0.25010324 0.48537517 0.69276094 0.55653465)
    > (setf *print-length* 20)

    20
    > (time (random-positions 10000))

    ; Evaluation took:
    ;   0.03 seconds of real time
    ;   0.026913 seconds of user run time
    ;   0.0 seconds of system run time
    ;   51,637,997 CPU cycles
    ;   0 page faults and
    ;   847,432 bytes consed.
    ; 
    (1483 1614 7412 9981 4944 6153 4549 9992 8890 805 ...)
    > 


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607