Won't that explode somewhat performance-wise once you have more than a handful of cards? It looks like something along the lines of O(n^2)...
Actually, the algorithm is O(n), it's essentially a list reversal with a call to random inserted. In psuedocode:
oldlist = [...]
newlist = []
if oldlist not empty
do
x = remove random from oldlist
insert x into newlist
repeat
(defun shuffle-in-place (l)
(cond ((null l) nil)
(t (rotatef (nth 0 l)
(nth (random (length l)) l))
(shuffle-in-place (rest l))))
l)
(defun shuffle (l)
(shuffle-in-place (copy-list l)))I do. Always.
One could use nconc instead of append, but that's not where the processor cycles are being lost as far as I can tell.
I'm also fairly certain there is no purely functional O(n) algorithm.
(defun nth (index list)
(if (zerop index)
(first index)
(nth (1- index) (rest list))))This is for you, since I've already had three today & the brainos in your nth implementation are a strong indication for its prescription:
http://www.espressoguide.net/resources/images/articles/A002I...
Cheers!