A simple Scheme shuffle

September 20, 2009
by Lee Spector (lspector)

Here’s a pretty simple definition for a function that shuffles a list, using almost only the functions and ideas that we’ve already covered in class and in the first couple of chapters of The Little Schemer. It’s a recursive definition in which we say that a shuffled list is just the list itself if the length of the list is less than 2, and¬†is¬†otherwise a randomly selected item from the list stuck onto the front of the result of shuffling the rest of the list. Notice that we can’t get the “rest of the list” by using cdr, as most of the examples in the book do, because we don’t want the list without its FIRST item — instead we want the list without whatever item it is that we’ve randomly selected. To do this I use two things that we haven’t yet seen in class, but they’re pretty straightforward: “let”, which is used to create local variables, and “remove”, which returns a list just like the list that you give it but without the first item that matches the item that you give it.

(define shuffle ; Returns a randomly re-ordered copy of list.
  (lambda (list)
    (if (< (length list) 2) 
        list
        (let ((item (list-ref list (random (length list)))))
          (cons item (shuffle (remove item list)))))))
(shuffle '(dark star crashes pouring its light into ashes))

=> (into dark its light pouring ashes star crashes)

-Lee

Tags:



Leave a Reply

You must be logged in to post a comment.