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.
Programming Praxis 
Here’s a PLT version, which works like the Perl version:
(define (shuffle x) (sort x #:key (lambda _ (random)) #:cache-keys? #t))
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
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))))To shuffle a linked list without converting it into an array or treating it as if it were an array, create two temporary lists, left and right, and then for each element in the original list, move that element randomly into either left or right. Then use recursion shuffle each of the left and right lists, combine them, and return the combined list.
Of course, doing two recursive calls can result in lots of memory usage, especially since the random selection could potentially put all elements of the original into left, or all into right… which adds to the stack depth, while accomplishing little work.
Instead, after partitioning into left and right, join the lists back together before shuffling, so that one of the two recursive calls can be changed into a loop.
Here’s some lisp code to do it:
(defun partition (before exclude) "Destructively randomly partition part of a list (starting with (rest BEFORE), up to, but not including, EXCLUDE) into two lists, which (concatenated together) are then inserted into the original list in their original place." ;(format t "Partition ~A ~A~%" before exclude) (do (lft rgt lend rend llen rlen) ((and lend rend) (setf (rest before) lft (rest lend) rgt (rest rend) exclude) (values rgt (< llen rlen))) ;(format t "partition, looping~%") (setf lft nil lend nil rgt nil rend nil llen 0 rlen 0) (do ((y (rest before) (rest y))) ((eq y exclude)) ; move each cons onto the end of either the left or ; right list, keeping track of where the list ends are. (if (zerop (random 2)) (and (incf llen) (if (not lft) (setf lft y lend y) (setf (rest lend) y lend y))) (and (incf rlen) (if (not rgt) (setf rgt y rend y) (setf (rest rend) y rend y))))))) (defun shuf-internal (before exclude) "Destructively shuffles the list which starts with (rest BEFORE), up to and excluding the cons EXCLUDE. Returns nothing." ;(format t "shuf-internal ~A ~A~%" before exclude) ; create a "working" list from mystart to myend, inclusive. ; Loop as long as the working list's length is > 1 (do () ((or (eq (rest before) exclude) (eq (cddr before) exclude)) (values 'foo!)) ;(format t "m-v-b~%") (multiple-value-bind (rgt rec-left) (partition before exclude) ;(format t "After part, before is ~A, rgt is ~A, doleft is ~A~%" before rgt rec-left) (if rec-left (progn (shuf-internal before rgt) (setf before rgt)) (progn (shuf-internal rgt exclude) (setf exclude rgt)))))) (defun nshuffle (thelist) (let ((dummyhead (cons 'dummy-head-value thelist))) (shuf-internal dummyhead nil) (rest dummyhead)))Alternatively, here’s some C code:
typedef struct node { int data; struct node * next; } node, *list; static void shl(list *before, node *after); void shufflelist(list * head) { if(head != NULL) shl(head, NULL); } #define RANDBOOL() (rand() > (RAND_MAX/2)) static void shl(list *before, node *after) { while( *before != after && (*before)->next != after ) { redo: list lft = NULL, rgt = NULL; node *lend = NULL, *rend = NULL; int llen = 0, rlen = 0; for( node *i = *before; i != after; i = i->next ) if( RANDBOOL() ) { if( lft ) lend->next = i; else lft = i; lend = i; ++llen; } else { if( rgt ) rend->next = i; else rgt = i; rend = i; ++rlen; } if( !lft || !rgt ) goto redo; *before = lft; lend->next = rgt; rend->next = after; if( llen < rlen ) { shl(before, rgt); before = &(rgt->next); } else { shl(rgt, after); after = rgt; } } }This would be used as:
PS: I’ve only tested the lisp code, since I’m still working on installing gcc on my computer.
But since the algorithm is the same, they should work the same.
I haven’t looked closely, but isn’t your algorithm O(n log n), like any other divide-and-conquer algorithm? The advantage of the list->vector->knuth-shuffle->list algorithm is that it works in O(n) time.
MY c IMPLEMENTATION
#include <stdlib.h> #include <time.h> static void swap(int arr[], int i, int j); void shuffle_array(int arr[], int n) { int i, j; srand((unsigned int)time(NULL)); for(j = n; j > 1; j--) { i = (rand() % j) + 1; swap(arr, i-1, j-1); } } void shuffle_linklist(List **p) { List *ptr, *currentp, *newp; int size, randnum; if(*p == NULL) return; /* calculate Linklist size */ for(size = 0, currentp = *p; currentp != NULL; size++, currentp = currentp->next); /* shuffle */ /* Shuffle single node */ srand((unsigned int)time(NULL)); randnum = (rand() % size) + 1; ptr = *p; currentp = *p; while(--randnum > 1) currentp = currentp->next; /* first node */ if(currentp == ptr) { ptr = ptr->next; *p = currentp; } else { *p = currentp->next; currentp->next = currentp->next->next; } (*p)->next; if(size == 1) return; /* shuffle remaining node */ for(size = size-1, currentp = ptr, newp = *p; size > 1; currentp = ptr, size--, newp = newp->next) { randnum = (rand() % size) + 1; while(--randnum > 1) currentp = currentp->next; /* first node */ if(currentp == ptr) { ptr = ptr->next; newp->next = currentp; } else { newp->next = currentp->next; currentp->next = currentp->next->next; } newp->next->next = NULL; } /* add last node */ newp->next = ptr; newp->next->next = NULL; } static void swap(int arr[], int i, int j) { int tmp; tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }