Advertisement
Advertisement


How do you rotate a two dimensional array?


Question

Inspired by Raymond Chen's post, say you have a 4x4 two dimensional array, write a function that rotates it 90 degrees. Raymond links to a solution in pseudo code, but I'd like to see some real world stuff.

[1][2][3][4]
[5][6][7][8]
[9][0][1][2]
[3][4][5][6]

Becomes:

[3][9][5][1]
[4][0][6][2]
[5][1][7][3]
[6][2][8][4]

Update: Nick's answer is the most straightforward, but is there a way to do it better than n^2? What if the matrix was 10000x10000?

2020/02/22
1
308
2/22/2020 5:25:33 PM

Accepted Answer

Here it is in C#

int[,] array = new int[4,4] {
    { 1,2,3,4 },
    { 5,6,7,8 },
    { 9,0,1,2 },
    { 3,4,5,6 }
};

int[,] rotated = RotateMatrix(array, 4);

static int[,] RotateMatrix(int[,] matrix, int n) {
    int[,] ret = new int[n, n];

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            ret[i, j] = matrix[n - j - 1, i];
        }
    }

    return ret;
}
2013/08/28
143
8/28/2013 8:07:29 PM


I’d like to add a little more detail. In this answer, key concepts are repeated, the pace is slow and intentionally repetitive. The solution provided here is not the most syntactically compact, it is however, intended for those who wish to learn what matrix rotation is and the resulting implementation.

Firstly, what is a matrix? For the purposes of this answer, a matrix is just a grid where the width and height are the same. Note, the width and height of a matrix can be different, but for simplicity, this tutorial considers only matrices with equal width and height (square matrices). And yes, matrices is the plural of matrix.

Example matrices are: 2×2, 3×3 or 5×5. Or, more generally, N×N. A 2×2 matrix will have 4 squares because 2×2=4. A 5×5 matrix will have 25 squares because 5×5=25. Each square is called an element or entry. We’ll represent each element with a period (.) in the diagrams below:

2×2 matrix

. .
. .

3×3 matrix

. . .
. . .
. . .

4×4 matrix

. . . .
. . . .
. . . .
. . . .

So, what does it mean to rotate a matrix? Let’s take a 2×2 matrix and put some numbers in each element so the rotation can be observed:

0 1
2 3

Rotating this by 90 degrees gives us:

2 0
3 1

We literally turned the whole matrix once to the right just like turning the steering wheel of a car. It may help to think of “tipping” the matrix onto its right side. We want to write a function, in Python, that takes a matrix and rotates in once to the right. The function signature will be:

def rotate(matrix):
    # Algorithm goes here.

The matrix will be defined using a two-dimensional array:

matrix = [
    [0,1],
    [2,3]
]

Therefore the first index position accesses the row. The second index position accesses the column:

matrix[row][column]

We’ll define a utility function to print a matrix.

def print_matrix(matrix):
    for row in matrix:
        print row

One method of rotating a matrix is to do it a layer at a time. But what is a layer? Think of an onion. Just like the layers of an onion, as each layer is removed, we move towards the center. Other analogies is a Matryoshka doll or a game of pass-the-parcel.

The width and height of a matrix dictate the number of layers in that matrix. Let’s use different symbols for each layer:

A 2×2 matrix has 1 layer

. .
. .

A 3×3 matrix has 2 layers

. . .
. x .
. . .

A 4×4 matrix has 2 layers

. . . .
. x x .
. x x .
. . . .

A 5×5 matrix has 3 layers

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

A 6×6 matrix has 3 layers

. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .

A 7×7 matrix has 4 layers

. . . . . . .
. x x x x x .
. x O O O x .
. x O - O x .
. x O O O x .
. x x x x x .
. . . . . . .

You may notice that incrementing the width and height of a matrix by one, does not always increase the number of layers. Taking the above matrices and tabulating the layers and dimensions, we see the number of layers increases once for every two increments of width and height:

+-----+--------+
| N×N | Layers |
+-----+--------+
| 1×1 |      1 |
| 2×2 |      1 |
| 3×3 |      2 |
| 4×4 |      2 |
| 5×5 |      3 |
| 6×6 |      3 |
| 7×7 |      4 |
+-----+--------+

However, not all layers need rotating. A 1×1 matrix is the same before and after rotation. The central 1×1 layer is always the same before and after rotation no matter how large the overall matrix:

+-----+--------+------------------+
| N×N | Layers | Rotatable Layers |
+-----+--------+------------------+
| 1×1 |      1 |                0 |
| 2×2 |      1 |                1 |
| 3×3 |      2 |                1 |
| 4×4 |      2 |                2 |
| 5×5 |      3 |                2 |
| 6×6 |      3 |                3 |
| 7×7 |      4 |                3 |
+-----+--------+------------------+

Given N×N matrix, how can we programmatically determine the number of layers we need to rotate? If we divide the width or height by two and ignore the remainder we get the following results.

+-----+--------+------------------+---------+
| N×N | Layers | Rotatable Layers |   N/2   |
+-----+--------+------------------+---------+
| 1×1 |      1 |                0 | 1/2 = 0 |
| 2×2 |      1 |                1 | 2/2 = 1 |
| 3×3 |      2 |                1 | 3/2 = 1 |
| 4×4 |      2 |                2 | 4/2 = 2 |
| 5×5 |      3 |                2 | 5/2 = 2 |
| 6×6 |      3 |                3 | 6/2 = 3 |
| 7×7 |      4 |                3 | 7/2 = 3 |
+-----+--------+------------------+---------+

Notice how N/2 matches the number of layers that need to be rotated? Sometimes the number of rotatable layers is one less the total number of layers in the matrix. This occurs when the innermost layer is formed of only one element (i.e. a 1×1 matrix) and therefore need not be rotated. It simply gets ignored.

We will undoubtedly need this information in our function to rotate a matrix, so let’s add it now:

def rotate(matrix):
    size = len(matrix)
    # Rotatable layers only.
    layer_count = size / 2

Now we know what layers are and how to determine the number of layers that actually need rotating, how do we isolate a single layer so we can rotate it? Firstly, we inspect a matrix from the outermost layer, inwards, to the innermost layer. A 5×5 matrix has three layers in total and two layers that need rotating:

. . . . .
. x x x .
. x O x .
. x x x .
. . . . .

Let’s look at columns first. The position of the columns defining the outermost layer, assuming we count from 0, are 0 and 4:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

0 and 4 are also the positions of the rows for the outermost layer.

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

This will always be the case since the width and height are the same. Therefore we can define the column and row positions of a layer with just two values (rather than four).

Moving inwards to the second layer, the position of the columns are 1 and 3. And, yes, you guessed it, it’s the same for rows. It’s important to understand we had to both increment and decrement the row and column positions when moving inwards to the next layer.

+-----------+---------+---------+---------+
|   Layer   |  Rows   | Columns | Rotate? |
+-----------+---------+---------+---------+
| Outermost | 0 and 4 | 0 and 4 | Yes     |
| Inner     | 1 and 3 | 1 and 3 | Yes     |
| Innermost | 2       | 2       | No      |
+-----------+---------+---------+---------+

So, to inspect each layer, we want a loop with both increasing and decreasing counters that represent moving inwards, starting from the outermost layer. We’ll call this our ‘layer loop’.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1
        print 'Layer %d: first: %d, last: %d' % (layer, first, last)

# 5x5 matrix
matrix = [
    [ 0, 1, 2, 3, 4],
    [ 5, 6, 6, 8, 9],
    [10,11,12,13,14],
    [15,16,17,18,19],
    [20,21,22,23,24]
]

rotate(matrix)

The code above loops through the (row and column) positions of any layers that need rotating.

Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3

We now have a loop providing the positions of the rows and columns of each layer. The variables first and last identify the index position of the first and last rows and columns. Referring back to our row and column tables:

+--------+-----------+
| Column | 0 1 2 3 4 |
+--------+-----------+
|        | . . . . . |
|        | . x x x . |
|        | . x O x . |
|        | . x x x . |
|        | . . . . . |
+--------+-----------+

+-----+-----------+
| Row |           |
+-----+-----------+
|   0 | . . . . . |
|   1 | . x x x . |
|   2 | . x O x . |
|   3 | . x x x . |
|   4 | . . . . . |
+-----+-----------+

So we can navigate through the layers of a matrix. Now we need a way of navigating within a layer so we can move elements around that layer. Note, elements never ‘jump’ from one layer to another, but they do move within their respective layers.

Rotating each element in a layer rotates the entire layer. Rotating all layers in a matrix rotates the entire matrix. This sentence is very important, so please try your best to understand it before moving on.

Now, we need a way of actually moving elements, i.e. rotate each element, and subsequently the layer, and ultimately the matrix. For simplicity, we’ll revert to a 3x3 matrix — that has one rotatable layer.

0 1 2
3 4 5
6 7 8

Our layer loop provides the indexes of the first and last columns, as well as first and last rows:

+-----+-------+
| Col | 0 1 2 |
+-----+-------+
|     | 0 1 2 |
|     | 3 4 5 |
|     | 6 7 8 |
+-----+-------+

+-----+-------+
| Row |       |
+-----+-------+
|   0 | 0 1 2 |
|   1 | 3 4 5 |
|   2 | 6 7 8 |
+-----+-------+

Because our matrices are always square, we need just two variables, first and last, since index positions are the same for rows and columns.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Our layer loop i=0, i=1, i=2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        # We want to move within a layer here.

The variables first and last can easily be used to reference the four corners of a matrix. This is because the corners themselves can be defined using various permutations of first and last (with no subtraction, addition or offset of those variables):

+---------------+-------------------+-------------+
| Corner        | Position          | 3x3 Values  |
+---------------+-------------------+-------------+
| top left      | (first, first)    | (0,0)       |
| top right     | (first, last)     | (0,2)       |
| bottom right  | (last, last)      | (2,2)       |
| bottom left   | (last, first)     | (2,0)       |
+---------------+-------------------+-------------+

For this reason, we start our rotation at the outer four corners — we’ll rotate those first. Let’s highlight them with *.

* 1 *
3 4 5
* 7 *

We want to swap each * with the * to the right of it. So let’s go ahead a print out our corners defined using only various permutations of first and last:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = (first, first)
        top_right = (first, last)
        bottom_right = (last, last)
        bottom_left = (last, first)

        print 'top_left: %s' % (top_left)
        print 'top_right: %s' % (top_right)
        print 'bottom_right: %s' % (bottom_right)
        print 'bottom_left: %s' % (bottom_left)

matrix = [
[0, 1, 2],
[3, 4, 5],
[6, 7, 8]
]

rotate(matrix)

Output should be:

top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)

Now we could quite easily swap each of the corners from within our layer loop:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2
    for layer in range(0, layer_count):

        first = layer
        last = size - first - 1

        top_left = matrix[first][first]
        top_right = matrix[first][last]
        bottom_right = matrix[last][last]
        bottom_left = matrix[last][first]

        # bottom_left -> top_left
        matrix[first][first] = bottom_left
        # top_left -> top_right
        matrix[first][last] = top_left
        # top_right -> bottom_right
        matrix[last][last] = top_right
        # bottom_right -> bottom_left
        matrix[last][first] = bottom_right


print_matrix(matrix)
print '---------'
rotate(matrix)
print_matrix(matrix)

Matrix before rotating corners:

[0, 1, 2]
[3, 4, 5]
[6, 7, 8]

Matrix after rotating corners:

[6, 1, 0]
[3, 4, 5]
[8, 7, 2]

Great! We have successfully rotated each corner of the matrix. But, we haven’t rotated the elements in the middle of each layer. Clearly we need a way of iterating within a layer.

The problem is, the only loop in our function so far (our layer loop), moves to the next layer on each iteration. Since our matrix has only one rotatable layer, the layer loop exits after rotating only the corners. Let’s look at what happens with a larger, 5×5 matrix (where two layers need rotating). The function code has been omitted, but it remains the same as above:

matrix = [
[0, 1, 2, 3, 4],
[5, 6, 7, 8, 9],
[10, 11, 12, 13, 14],
[15, 16, 17, 18, 19],
[20, 21, 22, 23, 24]
]
print_matrix(matrix)
print '--------------------'
rotate(matrix)
print_matrix(matrix)

The output is:

[20,  1,  2,  3,  0]
[ 5, 16,  7,  6,  9]
[10, 11, 12, 13, 14]
[15, 18, 17,  8, 19]
[24, 21, 22, 23,  4]

It shouldn’t be a surprise that the corners of the outermost layer have been rotated, but, you may also notice the corners of the next layer (inwards) have also been rotated. This makes sense. We’ve written code to navigate through layers and also to rotate the corners of each layer. This feels like progress, but unfortunately we must take a step back. It’s just no good moving onto the next layer until the previous (outer) layer has been fully rotated. That is, until each element in the layer has been rotated. Rotating only the corners won’t do!

Take a deep breath. We need another loop. A nested loop no less. The new, nested loop, will use the first and last variables, plus an offset to navigate within a layer. We’ll call this new loop our ‘element loop’. The element loop will visit each element along the top row, each element down the right side, each element along the bottom row and each element up the left side.

  • Moving forwards along the top row requires the column index to be incremented.
  • Moving down the right side requires the row index to be incremented.
  • Moving backwards along the bottom requires the column index to be decremented.
  • Moving up the left side requires the row index to be decremented.

This sounds complex, but it’s made easy because the number of times we increment and decrement to achieve the above remains the same along all four sides of the matrix. For example:

  • Move 1 element across the top row.
  • Move 1 element down the right side.
  • Move 1 element backwards along the bottom row.
  • Move 1 element up the left side.

This means we can use a single variable in combination with the first and last variables to move within a layer. It may help to note that moving across the top row and down the right side both require incrementing. While moving backwards along the bottom and up the left side both require decrementing.

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    # Move through layers (i.e. layer loop).
    for layer in range(0, layer_count):

            first = layer
            last = size - first - 1

            # Move within a single layer (i.e. element loop).
            for element in range(first, last):

                offset = element - first

                # 'element' increments column (across right)
                top_element = (first, element)
                # 'element' increments row (move down)
                right_side = (element, last)
                # 'last-offset' decrements column (across left)
                bottom = (last, last-offset)
                # 'last-offset' decrements row (move up)
                left_side = (last-offset, first)

                print 'top: %s' % (top)
                print 'right_side: %s' % (right_side)
                print 'bottom: %s' % (bottom)
                print 'left_side: %s' % (left_side)

Now we simply need to assign the top to the right side, right side to the bottom, bottom to the left side, and left side to the top. Putting this all together we get:

def rotate(matrix):
    size = len(matrix)
    layer_count = size / 2

    for layer in range(0, layer_count):
        first = layer
        last = size - first - 1

        for element in range(first, last):
            offset = element - first

            top = matrix[first][element]
            right_side = matrix[element][last]
            bottom = matrix[last][last-offset]
            left_side = matrix[last-offset][first]

            matrix[first][element] = left_side
            matrix[element][last] = top
            matrix[last][last-offset] = right_side
            matrix[last-offset][first] = bottom

Given the matrix:

0,  1,  2  
3,  4,  5  
6,  7,  8 

Our rotate function results in:

6,  3,  0  
7,  4,  1  
8,  5,  2  
2018/01/25

Python:

rotated = list(zip(*original[::-1]))

and counterclockwise:

rotated_ccw = list(zip(*original))[::-1]

How this works:

zip(*original) will swap axes of 2d arrays by stacking corresponding items from lists into new lists. (The * operator tells the function to distribute the contained lists into arguments)

>>> list(zip(*[[1,2,3],[4,5,6],[7,8,9]]))
[[1,4,7],[2,5,8],[3,6,9]]

The [::-1] statement reverses array elements (please see Extended Slices or this question):

>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]

Finally, combining the two will result in the rotation transformation.

The change in placement of [::-1] will reverse lists in different levels of the matrix.

2019/12/28

Here is one that does the rotation in place instead of using a completely new array to hold the result. I've left off initialization of the array and printing it out. This only works for square arrays but they can be of any size. Memory overhead is equal to the size of one element of the array so you can do the rotation of as large an array as you want.

int a[4][4];
int n = 4;
int tmp;
for (int i = 0; i < n / 2; i++)
{
    for (int j = i; j < n - i - 1; j++)
    {
        tmp             = a[i][j];
        a[i][j]         = a[j][n-i-1];
        a[j][n-i-1]     = a[n-i-1][n-j-1];
        a[n-i-1][n-j-1] = a[n-j-1][i];
        a[n-j-1][i]     = tmp;
    }
}
2017/06/13

There are tons of good code here but I just want to show what's going on geometrically so you can understand the code logic a little better. Here is how I would approach this.

first of all, do not confuse this with transposition which is very easy..

the basica idea is to treat it as layers and we rotate one layer at a time..

say we have a 4x4

1   2   3   4
5   6   7   8
9   10  11  12
13  14  15  16

after we rotate it clockwise by 90 we get

13  9   5   1
14  10  6   2   
15  11  7   3
16  12  8   4

so let's decompose this, first we rotate the 4 corners essentially

1           4


13          16

then we rotate the following diamond which is sort of askew

    2
            8
9       
        15

and then the 2nd skewed diamond

        3
5           
            12
    14

so that takes care of the outer edge so essentially we do that one shell at a time until

finally the middle square (or if it's odd just the final element which does not move)

6   7
10  11

so now let's figure out the indices of each layer, assume we always work with the outermost layer, we are doing

[0,0] -> [0,n-1], [0,n-1] -> [n-1,n-1], [n-1,n-1] -> [n-1,0], and [n-1,0] -> [0,0]
[0,1] -> [1,n-1], [1,n-2] -> [n-1,n-2], [n-1,n-2] -> [n-2,0], and [n-2,0] -> [0,1]
[0,2] -> [2,n-2], [2,n-2] -> [n-1,n-3], [n-1,n-3] -> [n-3,0], and [n-3,0] -> [0,2]

so on and so on until we are halfway through the edge

so in general the pattern is

[0,i] -> [i,n-i], [i,n-i] -> [n-1,n-(i+1)], [n-1,n-(i+1)] -> [n-(i+1),0], and [n-(i+1),0] to [0,i]
2013/11/25

As I said in my previous post, here's some code in C# that implements an O(1) matrix rotation for any size matrix. For brevity and readability there's no error checking or range checking. The code:

static void Main (string [] args)
{
  int [,]
    //  create an arbitrary matrix
    m = {{0, 1}, {2, 3}, {4, 5}};

  Matrix
    //  create wrappers for the data
    m1 = new Matrix (m),
    m2 = new Matrix (m),
    m3 = new Matrix (m);

  //  rotate the matricies in various ways - all are O(1)
  m1.RotateClockwise90 ();
  m2.Rotate180 ();
  m3.RotateAnitclockwise90 ();

  //  output the result of transforms
  System.Diagnostics.Trace.WriteLine (m1.ToString ());
  System.Diagnostics.Trace.WriteLine (m2.ToString ());
  System.Diagnostics.Trace.WriteLine (m3.ToString ());
}

class Matrix
{
  enum Rotation
  {
    None,
    Clockwise90,
    Clockwise180,
    Clockwise270
  }

  public Matrix (int [,] matrix)
  {
    m_matrix = matrix;
    m_rotation = Rotation.None;
  }

  //  the transformation routines
  public void RotateClockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 1) & 3);
  }

  public void Rotate180 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 2) & 3);
  }

  public void RotateAnitclockwise90 ()
  {
    m_rotation = (Rotation) (((int) m_rotation + 3) & 3);
  }

  //  accessor property to make class look like a two dimensional array
  public int this [int row, int column]
  {
    get
    {
      int
        value = 0;

      switch (m_rotation)
      {
      case Rotation.None:
        value = m_matrix [row, column];
        break;

      case Rotation.Clockwise90:
        value = m_matrix [m_matrix.GetUpperBound (0) - column, row];
        break;

      case Rotation.Clockwise180:
        value = m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column];
        break;

      case Rotation.Clockwise270:
        value = m_matrix [column, m_matrix.GetUpperBound (1) - row];
        break;
      }

      return value;
    }

    set
    {
      switch (m_rotation)
      {
      case Rotation.None:
        m_matrix [row, column] = value;
        break;

      case Rotation.Clockwise90:
        m_matrix [m_matrix.GetUpperBound (0) - column, row] = value;
        break;

      case Rotation.Clockwise180:
        m_matrix [m_matrix.GetUpperBound (0) - row, m_matrix.GetUpperBound (1) - column] = value;
        break;

      case Rotation.Clockwise270:
        m_matrix [column, m_matrix.GetUpperBound (1) - row] = value;
        break;
      }
    }
  }

  //  creates a string with the matrix values
  public override string ToString ()
  {
    int
      num_rows = 0,
      num_columns = 0;

    switch (m_rotation)
    {
    case Rotation.None:
    case Rotation.Clockwise180:
      num_rows = m_matrix.GetUpperBound (0);
      num_columns = m_matrix.GetUpperBound (1);
      break;

    case Rotation.Clockwise90:
    case Rotation.Clockwise270:
      num_rows = m_matrix.GetUpperBound (1);
      num_columns = m_matrix.GetUpperBound (0);
      break;
    }

    StringBuilder
      output = new StringBuilder ();

    output.Append ("{");

    for (int row = 0 ; row <= num_rows ; ++row)
    {
      if (row != 0)
      {
        output.Append (", ");
      }

      output.Append ("{");

      for (int column = 0 ; column <= num_columns ; ++column)
      {
        if (column != 0)
        {
          output.Append (", ");
        }

        output.Append (this [row, column].ToString ());
      }

      output.Append ("}");
    }

    output.Append ("}");

    return output.ToString ();
  }

  int [,]
    //  the original matrix
    m_matrix;

  Rotation
    //  the current view of the matrix
    m_rotation;
}

OK, I'll put my hand up, it doesn't actually do any modifications to the original array when rotating. But, in an OO system that doesn't matter as long as the object looks like it's been rotated to the clients of the class. At the moment, the Matrix class uses references to the original array data so changing any value of m1 will also change m2 and m3. A small change to the constructor to create a new array and copy the values to it will sort that out.

2013/08/28

Source: https://stackoverflow.com/questions/42519
Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow
Email: [email protected]