¿Cómo se rota una matriz bidimensional?

Inspirándote en la publicación de Raymond Chen , digamos que tienes una matriz bidimensional de 4x4, escribe una función que la gire 90 grados. Raymond enlaza a una solución en pseudocódigo, pero me gustaría ver algunas cosas del mundo real.

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

Se convierte en:

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

Actualización : la respuesta de Nick es la más sencilla, pero ¿hay alguna manera de hacerlo mejor que n^2? ¿Qué pasaría si la matriz fuera 10000x10000?

Sep 04 '08 03:09 swilliams

Me gustaría agregar un poco más de detalle. En esta respuesta se repiten conceptos clave, el ritmo es lento e intencionadamente repetitivo. La solución proporcionada aquí no es la más compacta sintácticamente; sin embargo, está destinada a aquellos que desean aprender qué es la rotación matricial y la implementación resultante.

En primer lugar, ¿qué es una matriz? Para los propósitos de esta respuesta, una matriz es solo una cuadrícula donde el ancho y el alto son iguales. Tenga en cuenta que el ancho y el alto de una matriz pueden ser diferentes, pero para simplificar, este tutorial considera solo matrices con el mismo ancho y alto ( matrices cuadradas ). Y sí, matrices es el plural de matriz.

Matrices de ejemplo son: 2×2, 3×3 o 5×5. O, más generalmente, N×N. Una matriz de 2×2 tendrá 4 cuadrados porque 2×2=4. Una matriz de 5×5 tendrá 25 cuadrados porque 5×5=25. Cada cuadrado se llama elemento o entrada. Representaremos cada elemento con un punto ( .) en los siguientes diagramas:

matriz 2×2

. .
. .

matriz 3×3

. . .
. . .
. . .

matriz 4×4

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

Entonces, ¿qué significa rotar una matriz? Tomemos una matriz de 2×2 y pongamos algunos números en cada elemento para que se pueda observar la rotación:

0 1
2 3

Girarlo 90 grados nos da:

2 0
3 1

Literalmente giramos toda la matriz una vez hacia la derecha, como si se girara el volante de un automóvil. Puede resultar útil pensar en “inclinar” la matriz hacia su lado derecho. Queremos escribir una función, en Python, que tome una matriz y la gire una vez hacia la derecha. La firma de la función será:

def rotate(matrix):
    # Algorithm goes here.

La matriz se definirá utilizando una matriz bidimensional:

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

Por lo tanto, la primera posición del índice accede a la fila. La segunda posición del índice accede a la columna:

matrix[row][column]

Definiremos una función de utilidad para imprimir una matriz.

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

Un método para rotar una matriz es hacerlo capa por capa. Pero ¿qué es una capa? Piensa en una cebolla. Al igual que las capas de una cebolla, a medida que vamos quitando cada capa vamos avanzando hacia el centro. Otras analogías son una muñeca Matryoshka o un juego de pasar el paquete.

El ancho y el alto de una matriz dictan el número de capas en esa matriz. Usemos diferentes símbolos para cada capa:

Una matriz de 2×2 tiene 1 capa

. .
. .

Una matriz de 3×3 tiene 2 capas.

. . .
. x .
. . .

Una matriz de 4×4 tiene 2 capas.

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

Una matriz de 5×5 tiene 3 capas

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

Una matriz de 6×6 tiene 3 capas

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

Una matriz de 7×7 tiene 4 capas

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

Puede notar que incrementar el ancho y el alto de una matriz en uno no siempre aumenta el número de capas. Tomando las matrices anteriores y tabulando las capas y dimensiones, vemos que el número de capas aumenta una vez por cada dos incrementos de ancho y alto:

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

Sin embargo, no es necesario rotar todas las capas. Una matriz de 1 × 1 es la misma antes y después de la rotación. La capa central de 1×1 es siempre la misma antes y después de la rotación, sin importar cuán grande sea la matriz general:

+-----+--------+------------------+
| 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 |
+-----+--------+------------------+

Dada la matriz N × N, ¿cómo podemos determinar mediante programación la cantidad de capas que necesitamos rotar? Si dividimos el ancho o el alto por dos e ignoramos el resto obtenemos los siguientes resultados.

+-----+--------+------------------+---------+
| 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 |
+-----+--------+------------------+---------+

¿Observa cómo N/2coincide el número de capas que deben rotarse? A veces, el número de capas giratorias es uno menos el número total de capas de la matriz. Esto ocurre cuando la capa más interna está formada por un solo elemento (es decir, una matriz de 1×1) y, por lo tanto, no es necesario girarla. Simplemente se ignora.

Sin duda necesitaremos esta información en nuestra función para rotar una matriz, así que agreguémosla ahora:

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

Ahora que sabemos qué son las capas y cómo determinar la cantidad de capas que realmente necesitan rotarse, ¿cómo aislamos una sola capa para poder rotarla? En primer lugar, inspeccionamos una matriz desde la capa más externa, hacia adentro, hasta la capa más interna. Una matriz de 5 × 5 tiene tres capas en total y dos capas que deben rotarse:

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

Veamos primero las columnas. La posición de las columnas que definen la capa más externa, suponiendo que contamos desde 0, son 0 y 4:

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

0 y 4 son también las posiciones de las filas de la capa más externa.

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

Este será siempre el caso ya que el ancho y el alto son los mismos. Por lo tanto, podemos definir las posiciones de las columnas y filas de una capa con solo dos valores (en lugar de cuatro).

Avanzando hacia la segunda capa, la posición de las columnas es 1 y 3. Y sí, lo has adivinado, es lo mismo para las filas. Es importante comprender que tuvimos que incrementar y disminuir las posiciones de las filas y columnas al avanzar a la siguiente capa.

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

Entonces, para inspeccionar cada capa, queremos un bucle con contadores crecientes y decrecientes que representen el movimiento hacia adentro, comenzando desde la capa más externa. A esto lo llamaremos nuestro "bucle de capa".

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)

El código anterior recorre las posiciones (fila y columna) de cualquier capa que necesite rotarse.

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 = (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  

Feb 16 '2016 16:02 Jack