In article <··········@lucy.ee.und.ac.za>,
Matthew C. Clarke <·······@unpsun1.cc.unp.ac.za> wrote:
>One of my post-grad students is doing a computational analysis of the
>game of Solitaire, and is looking for a good card shuffling algorithm.
(defun shuffle (sequence)
(sort (copy-seq sequence)
#'(lambda (x y)
(declare (ignore x y))
(zerop (random 2)))))
--David Gadbois
P.S.: Yes, it is a joke.
From: Carl M Kadie
Subject: Re: WANTED: Card shuffling algorithm
Date:
Message-ID: <CLnowF.4GM@cs.uiuc.edu>
Here is the shuffle code I use. It is linear and, I think, unbiased.
One thing though, when people shuffle, their shuffles are not unbiased
(cards tend to stay together).
- Carl
===========
(defun SHUFFLE (list)
" - C.M. Kadie
Returns a permutation and the length
Example:
(shuffle '(1 2 3 4 5 6 7 8 9 10))
;=> (2 8 5 1 7 3 10 6 4 9) 10;; for example
"
(let ((vector (apply #'vector list))
)
(dotimes (i (length vector) (values (vector-to-list vector) (length vector)))
(let ((ith (svref vector i))
(j (random (1+ i)))
)
(setf (svref vector i) (svref vector j))
(setf (svref vector j) ith)
))
))
--
Carl Kadie -- I do not represent any organization; this is just me.
= ·····@cs.uiuc.edu =
·····@cs.uiuc.edu (Carl M Kadie) writes:
>Here is the shuffle code I use....
>(defun SHUFFLE (list)
...
> (let ((vector (apply #'vector list))
... ^^^^^^^^^^^^^^^^^^^^^
That looks like a particularly bad way of making a vector out of a
list, especially if CALL-ARGUMENTS-LIMIT is less than (length list).
C-A-L can be as small as 50. Besides, that's exactly what
(coerce list 'simple-vector) is for.
> (let ((ith (svref vector i))
> (j (random (1+ i)))
> )
> (setf (svref vector i) (svref vector j))
> (setf (svref vector j) ith)
...
I think clarity is enhanced with
(let ((j (random (1+ i)))
(unless (= i j)
(rotatef (svref vector i) (svref vector j))))
and quite possibly speed, as well. I can't tell from CLtL2 whether
the test for (= i j) is necessary or not; it's certainly not desirable.
Dan Hoey
····@AIC.NRL.Navy.Mil