Shuffle

October 20, 2009

It is easy to shuffle an array by stepping through the array, swapping each element with a forward element (an element at an index greater than or equal to the current element) until the next-to-last element is reached. It is harder to shuffle a linked list, because lists don’t permit ready access to any element other than the first.

Your task is to write functions that shuffle an array and a linked list. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

Posted by programmingpraxis
Filed in Exercises
3 Comments »

3 Responses to “Shuffle”

  1. Sam TH said
    October 20, 2009 at 1:27 PM

    Here’s a PLT version, which works like the Perl version:

    (define (shuffle x) (sort x #:key (lambda _ (random)) #:cache-keys? #t))

  2. Ed Siok said
    October 22, 2009 at 3:21 PM

    Here’s an example of the array shuffle in perl (without using the pre-existing library). Perl doesn’t generally support linked lists as all arrays have the push/pop/etc functionality included.

    Perl array shuffle example

  3. Michel S. said
    October 27, 2009 at 9:54 PM

    Here is an implementation in Clojure. Its native datatypes are immutable, so for the array shuffle I’m using Java’s ArrayList. The collection shuffler works on any ordered Clojure collection (immutable lists as well as vectors); because values are immutable, we are modifying what the variables point to, which has to be done within a software transaction with dosync.

    (import 'java.util.ArrayList)

(defmulti shuffle type)

(defmethod shuffle ArrayList [#^ArrayList arr]
  (letfn [(swap!
	   [i j]
	   (let [t (.get arr i)]
	     (doto arr
	       (.set i (.get arr j))
	       (.set j t))))]
    (doseq [x (range (dec (.size arr)) -1 -1)]
      (swap! x (rand-int x)))
    arr))

;; alternate shuffler:
;; #(sort (fn [x y] (dec (rand-int 3))) %)

(defmethod shuffle clojure.lang.Ref [coll]
  (letfn [(shuffler
	   [coll]
	   (if (or (empty? coll) (empty? (next coll))) coll
	       (let [c (count coll)
		     pick (rand-int c)]
		 (cons (nth coll pick)
		       (concat (shuffler (take pick coll))
			       (shuffler (drop (inc pick) coll)))))))]

    (dosync (alter coll shuffler))))

Leave a Reply