## Matrix Rotation

### June 6, 2017

The first program creates a new matrix of the appropriate dimensions, then copies each item from the old matrix to the new matrix:

(define (rotate source) (let* ((n (matrix-rows source)) (m (matrix-cols source)) (target (make-matrix m n))) (for (i 0 m) (for (j 0 n) (matrix-set! target i j (matrix-ref source (- n j 1) i)))) target)) > (define m '#( #(a b c) #(d e f) #(g h i) #(j k l) #(m n o))) > (rotate m) #(#(m j g d a) #(n k h e b) #(o l i f c))

The second program uses a subroutine to swap four matrix items at once, at the four corners of a rectangle that successively visits each matrix item (except the center item in an odd-sized matrix):

(define (rotate! m) (define (rot4 m topleft topright botleft botright) (let ((t (matrix-ref m (car botright) (cdr botright)))) (matrix-set! m (car botright) (cdr botright) (matrix-ref m (car botleft) (cdr botleft))) (matrix-set! m (car botleft) (cdr botleft) (matrix-ref m (car topright) (cdr topright))) (matrix-set! m (car topright) (cdr topright) (matrix-ref m (car topleft) (cdr topleft))) (matrix-set! m (car topleft) (car topright) t))) (let ((n (matrix-rows m))) (for (i 0 (quotient n 2)) (let ((top i) (bottom (- n i 1)) (left i) (right (- n i 1))) (for (j 0 (- n i i 1)) (rot4 m (cons top (+ left j)) (cons (+ top j) right) (cons bottom (- right j)) (cons (- bottom j) left))))) m)) > (define m '#( #(a b c d e) #(f g h i j) #(k l m n o) #(p q r s t) #(u v w x y)) > (rotate! m) #(#(u p k f a) #(v q l g b) #(w r m h c) #(x s n i d) #(y t o j e)) > (rotate! m) #(#(y x w v u) #(t s r q p) #(o n m l k) #(j i h g f) #(e d c b a)) > (rotate! m) #(#(e j o t y) #(d i n s x) #(c h m r w) #(b g l q v) #(a f k p u)) > (rotate! m) #(#(a b c d e) #(f g h i j) #(k l m n o) #(p q r s t) #(u v w x y))

Four rotations restore the original matrix. It is remarkably easy to get mixed up between rows and columns while writing these functions. I did; don’t get discouraged if you do, too.

You can run the program at http://ideone.com/UoKFU2.

Advertisements

Pages: 1 2

The first part of the exercise in Python

Both parts of the exercise in Julia. Just a single generic method covering all possibilities.

function rotate{T <: Any}(X::Matrix{T})

n = size(X, 1)

n1 = n + 1

Y = X'

for i = 1:div(n, 2)

j = n1 – i

Y[:,i], Y[:,j] = Y[:,j], Y[:,i]

end

return Y

end

The second part in Python. The rotation is done by swapping two matrix elements at the time.

A better version of the second part. This version sets the matrix elements only once.

Klong version

Python 3.6.

rot() is basically the same as Paul’s.

rot_in_place() moves four corresponding elements at a time. ‘i’ can be thought of as the layer or ring, 0 being the outermost ring.

‘i’, ‘ir’, ‘j’, and ‘jr’ are the row or column indices of the elements being moved.

rot = lambda m:[*zip(*m[::-1])]

def rot_in_place(a):

n = len(a)

for i in range((n+1) // 2):

ir = -i-1

for j in range(i, n-i-1):

jr = -j-1

(a[i][j], a[j][ir],

a[jr][i],a[ir][jr]) = (a[jr][i], a[i][j],

a[ir][jr],a[j][ir])