Subject: Re: list of numbers in randomised order - prg. struggles at large (~10^5) numbers
From: rpw3@rpw3.org (Rob Warnock)
Date: Sat, 25 Mar 2006 20:26:20 -0600
Newsgroups: comp.lang.lisp
Message-ID: <QuudnQK5xuFRZrjZnZ2dnUVZ_tqdnZ2d@speakeasy.net>
Frank Buss  <fb@frank-buss.de> wrote:
+---------------
| David Sletten wrote:
| > Instead, I would suggest using a vector, which allows random access,
| > and the Fisher-Yates shuffle algorithm (see Knuth Vol. 2 Pg. 145).
...
| > (defun shuffle (v)
| >    (loop for j from (1- (length v)) downto 1
| >          for k = (random (1+ j))
| >          do (rotatef (aref v j) (aref v k)))
| >    v)
| 
| I think this is the fastest algorithm.
| 
| Another nice one I've read in this newsgroup some time ago
| (I don't remember where, but I remember the concept) :
| 
| (defun randomize (limit)
|   (mapcar #'car
|           (sort (loop for i from 0 below limit
|                       collect (cons i (random 1.0)))
|                 #'(lambda (x y) (< (cdr x) (cdr y))))))
+---------------

The pages <http://www.nist.gov/dads/HTML/fisherYatesShuffle.html>
and <http://www.nist.gov/dads/HTML/perfectShuffle.html> contain
comments on & references to why you don't want to do this. Briefly;

    Note: Attaching random tags then sorting (see permutation)
    may not be a perfect shuffle: if tags may be duplicated, a
    stable sort has a greater chance of producing permutations
    with some items in the original order.


-Rob

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