Last active
February 18, 2020 12:39
-
-
Save shortsightedsid/62d0ee21bfca53d9b69e to your computer and use it in GitHub Desktop.
Shuffle a list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
;; Easy Daily Programmer https://www.reddit.com/r/dailyprogrammer/comments/3e0hmh/20150720_challenge_224_easy_shuffling_a_list/ | |
(defun list-shuffler-recursive (input-list &optional accumulator) | |
"Shuffle a list using tail call recursion." | |
(if (eq input-list nil) | |
accumulator | |
(progn | |
(rotatef (car input-list) | |
(nth (random (length input-list)) input-list)) | |
(list-shuffler-recursive (cdr input-list) | |
(append accumulator (list (car input-list))))))) | |
(defun list-shuffler-iterative (input-list) | |
"Shuffle a list iteratively using a loop" | |
(loop with l = (length input-list) | |
for i below l | |
do (rotatef (nth i input-list) | |
(nth (random l) input-list))) | |
input-list) | |
(defun array-shuffler-iterative (input-array) | |
"Shuffle a array iteratively using a loop" | |
(loop with l = (length input-array) | |
for i below l | |
do (rotatef (aref input-array i) | |
(aref input-array (random l)))) | |
input-array) | |
;; The array based version is atleast 4 times faster than using lists. Both iterative versions do not cons any bytes in SBCL |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
I saw this someplace years ago, and I always laugh when I think about shuffling and this algorithm.