1

I am trying to understand the solution to rotating an N*N array by 90 degree in place. Here is the reference to the question that was asked earlier but is closed now - [link] How to rotate a matrix 90 degrees without using any extra space? The best voted answer looks pretty neat but i am not able to understand it enough can somebody pls explain these steps

Community
  • 1
  • 1
Sandy
  • 313
  • 1
  • 4
  • 13
  • 2
    [Here](http://imgur.com/vbc0bbd) is a gif I made that shows how elements are swapped during an in-place rotation. Maybe it will be of some use. – Kevin Mar 26 '13 at 19:40
  • 1
    Nice gif! Note, @Sandy, that the corner is square if N is even (`N / 2 == (N + 1) / 2`). – Pavel Anossov Mar 26 '13 at 19:42
  • thanks @Kevin :) Pavel i have started to understand this concept now - and i notice that in kevin's gif the whole program is trying to balance the first quadrant which triggers off like a chain reaction .. trying to place the onces whose position is taken up – Sandy Mar 26 '13 at 19:49

1 Answers1

1

It is using the XOR swap trick which is not needed in python since you can swap all four elements at once in a single expression:

def rot2(a):
    n = len(a)
    for x in range((n + 1) / 2):
        for y in range(n / 2):
            a[x][y], a[n-1-y][x], a[y][n-1-x], a[n-1-x][n-1-y] = (
                                                      a[y][n-1-x],
                                                      a[x][y], 
                                                      a[n-1-x][n-1-y],
                                                      a[n-1-y][x],
                                                 )

 

N×N matrix, N = 3:

1 2 3
4 5 6
7 8 9

N / 2 = 1, (N + 1)/2 = 2.

x = [0, 2) (0 or 1), y = [0, 1) (0).

Corner:

 1 2 | 3
_____|
 4 5   6
 7 8   9

Swaps: 1 ← 3 ← 7 ← 9 (← 1); 2 ← 6 ← 8 ← 4 (← 2)

 

5×5 matrix:

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

N / 2 = 2, (N + 1)/2 = 3.

x = [0, 3) (0 or 1 or 2), y = [0, 2) (0 or 1).

Corner:

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

Swaps:

a ← e ← y ← u
f ← d ← t ← v
b ← j ← x ← p
g ← i ← s ← q
c ← o ← w ← k
h ← n ← r ← l
Pavel Anossov
  • 60,842
  • 14
  • 151
  • 124
  • thanks @PavelAnossov can u tell me why are u looping only for n+1/2 – Sandy Mar 26 '13 at 18:59
  • 1
    I'm looping over one corner and swapping with the three other corners. – Pavel Anossov Mar 26 '13 at 19:01
  • range((n + 1) / 2) - in this command the inside part is computed just once and whole loop runs on the created list right? – Sandy Mar 26 '13 at 19:10
  • 1
    Yes. You can avoid creating a list altogether if you use `xrange` instead of `range`. Note: this code is for python 2. In python 3, `range` works like `xrange` and you have to use `//` instead of `/` for integer division. – Pavel Anossov Mar 26 '13 at 19:13
  • can u pls tell me how u are looping over one corner with range((n + 1) / 2) - I am unable to visualise – Sandy Mar 26 '13 at 19:13
  • thank you so much ... you dont know how much i was struggling to understand this :) can you also tell me how u arrived at this solution.. is it out of experience or is there something important to look out for in such problem (ps : i tried generalizing and writing my own function but couldnt) – Sandy Mar 26 '13 at 19:37
  • 1
    I just read the answers you linked and rewrote the top one in more concise python. I wouldn't trust myself with implementing a matrix operation from scratch, there's rarely a need to. Plenty of people already thought about it and tested it, why waste their effort? :) – Pavel Anossov Mar 26 '13 at 19:41