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.
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])