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

7 Responses to “Matrix Rotation”

  1. Jussi Piitulainen said
    ;;; Implement a matrix as a vector in row-major order, with width.
    
    (define imp::matrix-contents cdr)
    
    (define matrix-width car)
    (define (matrix-height m)
      (/ (vector-length (imp::matrix-contents m))
         (matrix-width m)))
    (define (make-matrix h w . o)
      (let ((o (if (null? o) #f (car o))))
        (cons w (make-vector (* h w) o))))
    (define (matrix-ref m r k)
      (vector-ref (imp::matrix-contents m) (+ (* (matrix-width m) r) k)))
    (define (matrix-set! m r k o)
      (vector-set! (imp::matrix-contents m) (+ (* (matrix-width m) r) k) o))
    
    ;;; Some of the points appear to go from (r, k) to (k, h - r - 1), so
    ;;; guess they all do. By linearity or something.
    
    (define (rot m)
      (let* ((h (matrix-height m))
             (w (matrix-width m))
             (m1 (make-matrix w h)))
        (do ((r 0 (+ r 1))) ((= r h))
          (do ((k 0 (+ k 1))) ((= k w))
            (matrix-set! m1 k (- h r 1) (matrix-ref m r k))))
        m1))
    
    ;;; At each (r, k) apply the rotating transformation to the four
    ;;; corresponding points at once. But this rotates the matrix four
    ;;; times! So only do half of the rows and half of the columns to
    ;;; rotate only once. Rounding both ways seems to work already.
    
    (define (rot! m)
      (let ((hw (matrix-height m)))
        (do ((r 0 (+ r 1))) ((= r (floor (/ hw 2))))
          (do ((k 0 (+ k 1))) ((= k (ceiling (/ hw 2))))
            (let* ((nr r)  (nk k)           (n (matrix-ref m nr nk))
                   (er nk) (ek (- hw nr 1)) (e (matrix-ref m er ek))
                   (sr ek) (sk (- hw er 1)) (s (matrix-ref m sr sk))
                   (wr sk) (wk (- hw sr 1)) (w (matrix-ref m wr wk)))
              (matrix-set! m er ek n)
              (matrix-set! m sr sk e)
              (matrix-set! m wr wk s)
              (matrix-set! m nr nk w))))))    
    
    ;;; Nice display for ocular inspection.
    
    (define (lay m)
      (let* ((w (matrix-width m))
             (h (matrix-height m)))
        (do ((r 0 (+ r 1))) ((= r h))
          (do ((k 0 (+ k 1))) ((= k w) (newline))
            (write-char #\space)
            (write (matrix-ref m r k))))))
    
    ;;; Test some. Caught a few thinkoes and a typo.
    
    (define A (cons 3 '#(a b c  d e f  g h i  j k l  m n o)))
    (define B (cons 5 (apply vector '(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))))
    (define C (cons 4 (apply vector '(a b c d  e f g h  i j k l  m n o p))))
    
    (lay A) (newline)
    (lay (rot A)) (newline)
    
    (lay B) (newline)
    (lay (rot B)) (newline)
    (rot! B) (lay B) (newline)
    
    (lay C) (newline)
    (lay (rot C)) (newline)
    (rot! C) (lay C) (newline)
    
  2. Paul said

    The first part of the exercise in Python

    def rot_right(matrix):
        return list(zip(*reversed(matrix)))
    
  3. Zack said

    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

  4. Paul said

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

    def rot_right_in_place(matrix):
        n = len(matrix)
        c = n-1
        size = (n+1)//2
        def rot(row, col):
            col0, row0, col, row = col, row, row, c - col
            matrix[row0][col0], matrix[row][col] = matrix[row][col], matrix[row0][col0]  # swap
            return row, col
        for i in range(size):
            for j in range(size if n % 2 == 0 else size-1):
                rot(*rot(*rot(i, j)))
    
  5. Paul said

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

    def rot_right_in_place(matrix):
        n = len(matrix)
        c = n-1
        size = (n+1)//2
        def rot(row, col):
            save = matrix[row][col]
            for _ in range(3):
                col0, row0, col, row = col, row, row, c - col
                matrix[row0][col0] = matrix[row][col]
            matrix[row][col] = save
        for i in range(size):
            for j in range(size if n % 2 == 0 else size-1):
                rot(i, j)
    
  6. Steve said

    Klong version

            :" assign array to a"
            a::[[:a :b :c] [:d :e :f] [:g :h :i] [:j :k :l] [:m :n :o]]
    [[:a :b :c] [:d :e :f] [:g :h :i] [:j :k :l] [:m :n :o]]
    
            |'+a   :"transpose the array and reverse each row"
    [[:m :j :g :d :a] [:n :k :h :e :b] [:o :l :i :f :c]]
            
            :" assign array to b"
            b::[[: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]]
    [[: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]]
    
            |'+b  :"transpose the array and reverse each row"
    [[: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]]
    
  7. Mike said

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: