A friend of mine passed me today a very good book Programming Pearls by Jon Bentley, in it I saw a method for rotating the elements of a vector that I just had to implement. Since I now mainly write java for work I decided to implement it in Lisp.

The method for rotating the vector is very simple and elegant it just holds in the following code.

To rotate an array of size N  by k positions

1. We start by reversing the first k elements, 
2.  Then we reverse the N-k last elements
3. Finally we reverse the whole array
   

 Its simple and completely fool proof its one  of those methods that just work out of the box, the code is so simple that it can not go wrong. If it appears unclear play around with some examples until it cliks in.

Here are the same three lines translated to lisp. 

 ;rotate by num elements the collection
(defun rot (collection num)
        (myreverse collection 0 num)
        (myreverse collection (+ num 1) (- (length collection) 1))
        (myreverse collection 0 (- (length collection) 1 ))
)

I decided not to use any libraries to make the example easier to understand  so here is the full code of a demo:

;Example of an in place N rot i in O(N)
;this implementation is as presented in programming pealrs by Jon Bentley

(setq arr (make-array 23))

;psedudo algo is as follows for all data i between start and end swap
(defun myreverse(data start end)
(dotimes (i (/ (- end start) 2))
(setq k (- end i))
(setq l (+ start i))
(swap data k l)
)
)

;standard swapping of two elements in a vector
(defun swap(vect i j)
(setq temp (aref vect i))
(setf (aref vect i) (aref vect j))
(setf (aref vect j) temp)
)


;rotate by num elements the collection
(defun rot (collection num)
(myreverse collection 0 num)
(myreverse collection (+ num 1) (- (length collection) 1))
(myreverse collection 0 (- (length collection) 1 ))
)

;initialising the collection with simple integers
(dotimes (i (length arr))
(setf (aref arr i) i)
)

;invoking the rotation of five elements
(print "Before: " )
(print  arr)

(print "(rot arr 5)" )
(rot arr 5)
(print "After: " )
(print arr)

Running it in your favoutite Lisp interpreter will give you:


prozak@Mistral:~/Exploration/lisp/pearls%clisp rot.lisp

"Before: "
#(0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22)
"(rot arr 5)"
"After: "
#(6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 0 1 2 3 4 5)



There is some inherent beauty in the simple basic elements of programming, today I had the chance to re-discover the basics. Wonder what it will be like if I finally get round to read Knuth's books. ;-)