algorithm - two - ¿Cómo se gira una matriz bidimensional?
que son matrices de rotacion (30)
Aquí está en 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;
}
Inspirado por la publicación de Raymond Chen , digamos que tienes una matriz bidimensional 4x4, escribe una función que gire 90 grados. Raymond se enlaza con una solución en pseudo có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 directa, pero ¿hay alguna manera de hacerlo mejor que n ^ 2? ¿Y si la matriz fuera 10000x10000?
Aquí hay uno que hace la rotación en su lugar en lugar de usar una matriz completamente nueva para mantener el resultado. He dejado de inicializar la matriz e imprimirla. Esto solo funciona para matrices cuadradas, pero pueden ser de cualquier tamaño. La sobrecarga de memoria es igual al tamaño de un elemento de la matriz, por lo que puede hacer la rotación de una matriz tan grande como desee.
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;
}
}
Como dije en mi publicación anterior, aquí hay un código en C # que implementa una rotación de matriz O (1) para cualquier matriz de tamaño. Para mayor brevedad y facilidad de lectura, no hay verificación de errores o verificación de rango. El código:
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;
}
Bien, voy a levantar la mano, en realidad no hace ninguna modificación a la matriz original al girar. Pero, en un sistema OO, no importa siempre que el objeto parezca haber sido girado a los clientes de la clase. En este momento, la clase Matrix utiliza referencias a los datos de la matriz original, por lo que cambiar cualquier valor de m1 también cambiará m2 y m3. Un pequeño cambio en el constructor para crear una nueva matriz y copiar los valores al mismo lo solucionará.
Esta es una mejor versión de Java: lo hice para una matriz con un ancho y alto diferente
- h es aquí la altura de la matriz después de girar
- w es aquí el ancho de la matriz después de girar
public int[][] rotateMatrixRight(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[w - j - 1][i];
}
}
return ret;
}
public int[][] rotateMatrixLeft(int[][] matrix)
{
/* W and H are already swapped */
int w = matrix.length;
int h = matrix[0].length;
int[][] ret = new int[h][w];
for (int i = 0; i < h; ++i) {
for (int j = 0; j < w; ++j) {
ret[i][j] = matrix[j][h - i - 1];
}
}
return ret;
}
Este código se basa en la publicación de Nick Berardi.
Hay un montón de buen código aquí, pero solo quiero mostrar lo que sucede geométricamente para que puedas entender un poco mejor la lógica del código. Aquí es cómo me acercaría a esto.
En primer lugar, no confunda esto con la transposición, que es muy fácil.
La idea básica es tratarla como capas y rotamos una capa a la vez.
Digamos que tenemos un 4x4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
después de que lo giramos en sentido horario por 90 obtenemos
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
Así que vamos a descomponer esto, primero rotamos las 4 esquinas esencialmente
1 4
13 16
luego giramos el siguiente diamante que es algo torcido
2
8
9
15
y luego el segundo diamante torcido
3
5
12
14
por lo que cuida el borde exterior, así que esencialmente hacemos que una concha a la vez hasta
finalmente, el cuadrado central (o si es extraño, solo el elemento final que no se mueve)
6 7
10 11
así que ahora vamos a averiguar los índices de cada capa, asumamos que siempre trabajamos con la capa más externa, estamos haciendo
[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]
así sucesivamente hasta que estemos a medio camino a través del borde
así que en general el patrón es
[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]
Me gustaría añadir un poco más de detalle. En esta respuesta, los conceptos clave se repiten, el ritmo es lento e intencionalmente repetitivo. La solución aquí provista no es la más compacta sintácticamente, sin embargo, está destinada a aquellos que desean aprender qué es la rotación de matrices 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 la altura 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 igual ancho y alto ( matrices cuadradas ). Y sí, matrices es el plural de la matriz.
Ejemplos de matrices 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 diagramas a continuación:
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
Girando esto 90 grados nos da:
2 0
3 1
Literalmente giramos toda la matriz una vez a la derecha, igual que al girar el volante de un automóvil. Puede ayudar pensar en “inclinar” la matriz hacia su lado derecho. Queremos escribir una función, en Python, que toma una matriz y gira una vez a 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 se elimina cada capa, nos movemos 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 observar que al aumentar 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 la cantidad 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 todas las capas necesitan ser rotadas. 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 qué tan 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 el número de capas que necesitamos rotar? Si dividimos el ancho o la altura 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/2 coincide con 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 en 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.
Indudablemente, 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 ser rotadas, ¿cómo aislamos una sola capa para que podamos rotarla? En primer lugar, inspeccionamos una matriz desde la capa más externa, hacia el interior, hasta la capa más interna. Una matriz de 5 × 5 tiene tres capas en total y dos capas que necesitan rotación:
. . . . .
. 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, asumiendo 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 para la capa más externa.
+-----+-----------+
| Row | |
+-----+-----------+
| 0 | . . . . . |
| 1 | . x x x . |
| 2 | . x O x . |
| 3 | . x x x . |
| 4 | . . . . . |
+-----+-----------+
Este siempre será el caso ya que el ancho y la altura son los mismos. Por lo tanto, podemos definir las posiciones de columna y fila de una capa con solo dos valores (en lugar de cuatro).
Moviéndose hacia el interior de la segunda capa, la posición de las columnas es 1 y 3. Y, sí, lo has adivinado, es la misma para las filas. Es importante entender que tuvimos que incrementar y disminuir las posiciones de las filas y columnas al avanzar hacia 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 representan moverse hacia adentro, comenzando desde la capa más externa. Llamaremos a esto 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 rotación.
Layer 0: first: 0, last: 4
Layer 1: first: 1, last: 3
Ahora tenemos un bucle que proporciona las posiciones de las filas y columnas de cada capa. Las variables first y last identifican la posición del índice de las primeras y últimas filas y columnas. Refiriéndonos a nuestras tablas de filas y columnas:
+--------+-----------+
| 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 | . . . . . |
+-----+-----------+
Así podemos navegar a través de las capas de una matriz. Ahora necesitamos una forma de navegar dentro de una capa para poder mover elementos alrededor de esa capa. Tenga en cuenta que los elementos nunca "saltan" de una capa a otra, pero sí se mueven dentro de sus respectivas capas.
Girando cada elemento en una capa rota la capa completa. Al rotar todas las capas en una matriz, se gira toda la matriz. Esta oración es muy importante, así que por favor intente entenderla antes de continuar.
Ahora, necesitamos una forma de mover realmente los elementos, es decir, rotar cada elemento, y posteriormente la capa, y finalmente la matriz. Para simplificar, volveremos a una matriz de 3x3, que tiene una capa giratoria.
0 1 2
3 4 5
6 7 8
Nuestro bucle de capa proporciona los índices de las primeras y últimas columnas, así como las primeras y últimas filas:
+-----+-------+
| 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 |
+-----+-------+
Debido a que nuestras matrices son siempre cuadradas, necesitamos solo dos variables, la first y la last , ya que las posiciones de índice son las mismas para filas y columnas.
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.
Las variables primera y última se pueden usar fácilmente para hacer referencia a las cuatro esquinas de una matriz. Esto se debe a que las esquinas en sí pueden definirse utilizando varias permutaciones de la first y la last (sin restar, sumar o compensar esas 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) |
+---------------+-------------------+-------------+
Por esta razón, comenzamos nuestra rotación en las cuatro esquinas exteriores, las rotaremos primero. Vamos a resaltarlos con * .
* 1 *
3 4 5
* 7 *
Queremos intercambiar cada * con el * a la derecha. Así que avancemos para imprimir nuestras esquinas definidas usando solo varias permutaciones de la first y la 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)
La salida debe ser:
top_left: (0, 0)
top_right: (0, 2)
bottom_right: (2, 2)
bottom_left: (2, 0)
Ahora podríamos intercambiar fácilmente cada una de las esquinas dentro de 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
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)
Matriz antes de girar esquinas:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
Matriz después de rotar esquinas:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
¡Genial! Hemos rotado con éxito cada esquina de la matriz. Pero, no hemos girado los elementos en el medio de cada capa. Claramente necesitamos una forma de iterar dentro de una capa.
El problema es que el único bucle en nuestra función hasta ahora (nuestro bucle de capa), se mueve a la siguiente capa en cada iteración. Como nuestra matriz solo tiene una capa giratoria, el bucle de capa sale después de rotar solo las esquinas. Veamos lo que sucede con una matriz más grande, 5 × 5 (donde dos capas necesitan rotación). El código de función se ha omitido, pero sigue siendo el mismo que el anterior:
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)
La salida es:
[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]
No debería sorprender que las esquinas de la capa más externa hayan sido rotadas, pero también es posible que note que las esquinas de la siguiente capa (hacia adentro) también hayan sido rotadas. Esto tiene sentido. Hemos escrito código para navegar a través de las capas y también para rotar las esquinas de cada capa. Esto se siente como un progreso, pero desafortunadamente debemos dar un paso atrás. Simplemente no es bueno pasar a la siguiente capa hasta que la capa anterior (externa) haya sido completamente rotada. Es decir, hasta que se haya girado cada elemento de la capa. ¡Rotar solo las esquinas no sirve!
Tomar una respiración profunda. Necesitamos otro bucle. Un bucle anidado no menos. El nuevo bucle anidado utilizará la first y la last variable, más un desplazamiento para navegar dentro de una capa. Llamaremos a este nuevo bucle nuestro ''bucle de elemento''. El bucle de elementos visitará cada elemento a lo largo de la fila superior, cada elemento en el lado derecho, cada elemento a lo largo de la fila inferior y cada elemento en el lado izquierdo.
- Avanzar a lo largo de la fila superior requiere que se incremente el índice de la columna.
- Mover hacia abajo el lado derecho requiere que el índice de fila se incremente.
- Moverse hacia atrás a lo largo de la parte inferior requiere que el índice de la columna disminuya.
- Mover hacia arriba el lado izquierdo requiere que se disminuya el índice de la fila.
Esto suena complejo, pero es fácil porque la cantidad de veces que incrementamos y disminuimos para lograr lo anterior sigue siendo la misma en los cuatro lados de la matriz. Por ejemplo:
- Mueve 1 elemento a través de la fila superior.
- Mueve 1 elemento por el lado derecho.
- Mueve 1 elemento hacia atrás a lo largo de la fila inferior.
- Mueve 1 elemento por el lado izquierdo.
Esto significa que podemos usar una sola variable en combinación con la first y la last variable para movernos dentro de una capa. Puede ser útil tener en cuenta que moverse en la fila superior y hacia abajo en el lado derecho requiere un incremento. Mientras se desplaza hacia atrás a lo largo de la parte inferior y hacia arriba del lado izquierdo, ambos requieren una disminución.
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)
Ahora simplemente debemos asignar la parte superior al lado derecho, el lado derecho a la parte inferior, la parte inferior al lado izquierdo y el lado izquierdo a la parte superior. Poniendo todo esto juntos obtenemos:
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
Dada la matriz:
0, 1, 2
3, 4, 5
6, 7, 8
Nuestra función de rotate da como resultado:
6, 3, 0
7, 4, 1
8, 5, 2
PHP:
<?php
$a = array(array(1,2,3,4),array(5,6,7,8),array(9,0,1,2),array(3,4,5,6));
$b = array(); //result
while(count($a)>0)
{
$b[count($a[0])-1][] = array_shift($a[0]);
if (count($a[0])==0)
{
array_shift($a);
}
}
?>
Si bien la rotación de los datos en su lugar podría ser necesaria (quizás para actualizar la representación almacenada físicamente), se vuelve más simple y posiblemente más eficaz para agregar una capa de direccionamiento indirecto al acceso a la matriz, tal vez una interfaz:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Si su Matrix ya implementa esta interfaz, entonces se puede rotar a través de una clase decorator como esta:
class RotatedMatrix : IReadableMatrix
{
private readonly IReadableMatrix _baseMatrix;
public RotatedMatrix(IReadableMatrix baseMatrix)
{
_baseMatrix = baseMatrix;
}
int GetValue(int x, int y)
{
// transpose x and y dimensions
return _baseMatrix(y, x);
}
}
Girando + 90 / -90 / 180 grados, volteando horizontalmente / verticalmente y la escala también se puede lograr de esta manera.
El desempeño debería ser medido en su escenario específico. Sin embargo, la operación O (n ^ 2) ahora se ha reemplazado con una llamada O (1). Es una llamada de método virtual que es más lenta que el acceso directo a la matriz, por lo que depende de la frecuencia con la que se utiliza la matriz rotada después de la rotación. Si se usa una vez, entonces este enfoque definitivamente ganaría. Si se gira, entonces se usa en un sistema de larga duración durante días, entonces la rotación en el lugar podría funcionar mejor. También depende de si puede aceptar el costo inicial.
Al igual que con todos los problemas de rendimiento, medir, medir, medir!
#transpose es un método estándar de la clase Array de Ruby, por lo tanto:
% irb
irb(main):001:0> m = [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
=> [[1, 2, 3, 4], [5, 6, 7, 8], [9, 0, 1, 2], [3, 4, 5, 6]]
irb(main):002:0> m.reverse.transpose
=> [[3, 9, 5, 1], [4, 0, 6, 2], [5, 1, 7, 3], [6, 2, 8, 4]]
La implementación es una función de transposición n ^ 2 escrita en C. Puede verla aquí: http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose "clic para alternar la fuente "al lado de" transponer ".
Recuerdo mejores soluciones que O (n ^ 2), pero solo para matrices especialmente construidas (como matrices dispersas)
Nick''s respuesta Nick''s también funcionaría para una matriz NxM con solo una pequeña modificación (a diferencia de una NxN).
string[,] orig = new string[n, m];
string[,] rot = new string[m, n];
...
for ( int i=0; i < n; i++ )
for ( int j=0; j < m; j++ )
rot[j, n - i - 1] = orig[i, j];
Una forma de pensar sobre esto es que ha movido el centro del eje (0,0) desde la esquina superior izquierda a la esquina superior derecha. Simplemente estás transponiendo de uno a otro.
For i:= 0 to X do For j := 0 to X do graphic[j][i] := graphic2[Xi][j]
X es el tamaño de la matriz en la que se encuentra el gráfico.
O (n ^ 2) tiempo y O (1) algoritmo de espacio (¡sin ningún tipo de solución y cosas de pañuelo!)
Girar en +90:
- Transponer
- Invierta cada fila
Girar en -90:
Método 1 :
- Transponer
- Invertir cada columna
Método 2:
- Invierta cada fila
- Transponer
Girar en +180:
Método 1 : Gira +90 dos veces
Método 2 : Invierta cada fila y luego invierta cada columna (Transposición)
Girar por -180:
Método 1 : rotar por -90 dos veces
Método 2 : Invierta cada columna y luego invierta cada fila
Método 3 : Gire en +180 ya que son iguales
Pitón:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
Barato, lo sé.
Y a la izquierda:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Cómo funciona esto: (Solicitado en comentarios)
zip(*original) intercambiará ejes de matrices 2d al apilar los elementos correspondientes de las listas en nuevas listas. (El operador * le dice a la función que distribuya las listas contenidas en argumentos)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
La instrucción [::-1] invierte los elementos de la matriz (consulte las secciones ampliadas ).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
Finalmente, combinando los dos resultará en la transformación de rotación.
El cambio en la ubicación de [::-1] revertirá las listas en diferentes niveles de la matriz.
Aquí está la versión de Java:
public static void rightRotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) {
int first = layer;
int last = n - 1 - first;
for (int i = first; i < last; i++) {
int offset = i - first;
int temp = matrix[first][i];
matrix[first][i] = matrix[last-offset][first];
matrix[last-offset][first] = matrix[last][last-offset];
matrix[last][last-offset] = matrix[i][last];
matrix[i][last] = temp;
}
}
}
el método primero rota la capa de mostouter, luego se mueve hacia la capa interna de manera cuadrada.
Aquí está mi implementación In Place en C
void rotateRight(int matrix[][SIZE], int length) {
int layer = 0;
for (int layer = 0; layer < length / 2; ++layer) {
int first = layer;
int last = length - 1 - layer;
for (int i = first; i < last; ++i) {
int topline = matrix[first][i];
int rightcol = matrix[i][last];
int bottomline = matrix[last][length - layer - 1 - i];
int leftcol = matrix[length - layer - 1 - i][first];
matrix[first][i] = leftcol;
matrix[i][last] = topline;
matrix[last][length - layer - 1 - i] = rightcol;
matrix[length - layer - 1 - i][first] = bottomline;
}
}
}
Aquí está mi intento de rotación de 90 grados en la matriz, que es una solución de 2 pasos en C. Primero, transponga la matriz en su lugar y luego intercambie las columnas.
#define ROWS 5
#define COLS 5
void print_matrix_b(int B[][COLS], int rows, int cols)
{
for (int i = 0; i <= rows; i++) {
for (int j = 0; j <=cols; j++) {
printf("%d ", B[i][j]);
}
printf("/n");
}
}
void swap_columns(int B[][COLS], int l, int r, int rows)
{
int tmp;
for (int i = 0; i <= rows; i++) {
tmp = B[i][l];
B[i][l] = B[i][r];
B[i][r] = tmp;
}
}
void matrix_2d_rotation(int B[][COLS], int rows, int cols)
{
int tmp;
// Transpose the matrix first
for (int i = 0; i <= rows; i++) {
for (int j = i; j <=cols; j++) {
tmp = B[i][j];
B[i][j] = B[j][i];
B[j][i] = tmp;
}
}
// Swap the first and last col and continue until
// the middle.
for (int i = 0; i < (cols / 2); i++)
swap_columns(B, i, cols - i, rows);
}
int _tmain(int argc, _TCHAR* argv[])
{
int B[ROWS][COLS] = {
{1, 2, 3, 4, 5},
{6, 7, 8, 9, 10},
{11, 12, 13, 14, 15},
{16, 17, 18, 19, 20},
{21, 22, 23, 24, 25}
};
matrix_2d_rotation(B, ROWS - 1, COLS - 1);
print_matrix_b(B, ROWS - 1, COLS -1);
return 0;
}
Aquí está mi versión de Ruby (tenga en cuenta que los valores no se muestran igual, pero aún gira como se describe).
def rotate(matrix)
result = []
4.times { |x|
result[x] = []
4.times { |y|
result[x][y] = matrix[y][3 - x]
}
}
result
end
matrix = []
matrix[0] = [1,2,3,4]
matrix[1] = [5,6,7,8]
matrix[2] = [9,0,1,2]
matrix[3] = [3,4,5,6]
def print_matrix(matrix)
4.times { |y|
4.times { |x|
print "#{matrix[x][y]} "
}
puts ""
}
end
print_matrix(matrix)
puts ""
print_matrix(rotate(matrix))
La salida:
1 5 9 3
2 6 0 4
3 7 1 5
4 8 2 6
4 3 2 1
8 7 6 5
2 1 0 9
6 5 4 3
Código C # para rotar [n, m] matrices 2D 90 grados a la derecha
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace MatrixProject
{
// mattrix class
class Matrix{
private int rows;
private int cols;
private int[,] matrix;
public Matrix(int n){
this.rows = n;
this.cols = n;
this.matrix = new int[this.rows,this.cols];
}
public Matrix(int n,int m){
this.rows = n;
this.cols = m;
this.matrix = new int[this.rows,this.cols];
}
public void Show()
{
for (var i = 0; i < this.rows; i++)
{
for (var j = 0; j < this.cols; j++) {
Console.Write("{0,3}", this.matrix[i, j]);
}
Console.WriteLine();
}
}
public void ReadElements()
{
for (var i = 0; i < this.rows; i++)
for (var j = 0; j < this.cols; j++)
{
Console.Write("element[{0},{1}]=",i,j);
this.matrix[i, j] = Convert.ToInt32(Console.ReadLine());
}
}
// rotate [n,m] 2D array by 90 deg right
public void Rotate90DegRight()
{
// create a mirror of current matrix
int[,] mirror = this.matrix;
// create a new matrix
this.matrix = new int[this.cols, this.rows];
for (int i = 0; i < this.rows; i++)
{
for (int j = 0; j < this.cols; j++)
{
this.matrix[j, this.rows - i - 1] = mirror[i, j];
}
}
// replace cols count with rows count
int tmp = this.rows;
this.rows = this.cols;
this.cols = tmp;
}
}
class Program
{
static void Main(string[] args)
{
Matrix myMatrix = new Matrix(3,4);
Console.WriteLine("Enter matrix elements:");
myMatrix.ReadElements();
Console.WriteLine("Matrix elements are:");
myMatrix.Show();
myMatrix.Rotate90DegRight();
Console.WriteLine("Matrix rotated at 90 deg are:");
myMatrix.Show();
Console.ReadLine();
}
}
}
Resultado:
Enter matrix elements:
element[0,0]=1
element[0,1]=2
element[0,2]=3
element[0,3]=4
element[1,0]=5
element[1,1]=6
element[1,2]=7
element[1,3]=8
element[2,0]=9
element[2,1]=10
element[2,2]=11
element[2,3]=12
Matrix elements are:
1 2 3 4
5 6 7 8
9 10 11 12
Matrix rotated at 90 deg are:
9 5 1
10 6 2
11 7 3
12 8 4
Código C para la rotación de la matriz 90 grados en el sentido de las agujas del reloj EN LUGAR para cualquier matriz M * N
void rotateInPlace(int * arr[size][size], int row, int column){
int i, j;
int temp = row>column?row:column;
int flipTill = row < column ? row : column;
for(i=0;i<flipTill;i++){
for(j=0;j<i;j++){
swapArrayElements(arr, i, j);
}
}
temp = j+1;
for(i = row>column?i:0; i<row; i++){
for(j=row<column?temp:0; j<column; j++){
swapArrayElements(arr, i, j);
}
}
for(i=0;i<column;i++){
for(j=0;j<row/2;j++){
temp = arr[i][j];
arr[i][j] = arr[i][row-j-1];
arr[i][row-j-1] = temp;
}
}
}
Desde un punto de vista lineal, considere las matrices:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
Ahora toma una transposición
1 4 7
A'' = 2 5 8
3 6 9
Y considere la acción de A ''en B, o B en A''.
Respectivamente:
7 4 1 3 6 9
A''B = 8 5 2 BA'' = 2 5 8
9 6 3 1 4 7
Esto es expandible para cualquier matriz nxn. Y aplicando este concepto rápidamente en el código:
void swapInSpace(int** mat, int r1, int c1, int r2, int c2)
{
mat[r1][c1] ^= mat[r2][c2];
mat[r2][c2] ^= mat[r1][c1];
mat[r1][c1] ^= mat[r2][c2];
}
void transpose(int** mat, int size)
{
for (int i = 0; i < size; i++)
{
for (int j = (i + 1); j < size; j++)
{
swapInSpace(mat, i, j, j, i);
}
}
}
void rotate(int** mat, int size)
{
//Get transpose
transpose(mat, size);
//Swap columns
for (int i = 0; i < size / 2; i++)
{
for (int j = 0; j < size; j++)
{
swapInSpace(mat, i, j, size - (i + 1), j);
}
}
}
Esta es mi implementación, en C, O (1) memoria de complejidad, rotación en el lugar, 90 grados en el sentido de las agujas del reloj:
#include <stdio.h>
#define M_SIZE 5
static void initMatrix();
static void printMatrix();
static void rotateMatrix();
static int m[M_SIZE][M_SIZE];
int main(void){
initMatrix();
printMatrix();
rotateMatrix();
printMatrix();
return 0;
}
static void initMatrix(){
int i, j;
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
m[i][j] = M_SIZE*i + j + 1;
}
}
}
static void printMatrix(){
int i, j;
printf("Matrix/n");
for(i = 0; i < M_SIZE; i++){
for(j = 0; j < M_SIZE; j++){
printf("%02d ", m[i][j]);
}
printf("/n");
}
printf("/n");
}
static void rotateMatrix(){
int r, c;
for(r = 0; r < M_SIZE/2; r++){
for(c = r; c < M_SIZE - r - 1; c++){
int tmp = m[r][c];
m[r][c] = m[M_SIZE - c - 1][r];
m[M_SIZE - c - 1][r] = m[M_SIZE - r - 1][M_SIZE - c - 1];
m[M_SIZE - r - 1][M_SIZE - c - 1] = m[c][M_SIZE - r - 1];
m[c][M_SIZE - r - 1] = tmp;
}
}
}
Implementación de pseudocódigo +90 de hoyuelo (por ejemplo, transposición y luego revertir cada fila) en JavaScript:
function rotate90(a){
// transpose from http://www.codesuck.com/2012/02/transpose-javascript-array-in-one-line.html
a = Object.keys(a[0]).map(function (c) { return a.map(function (r) { return r[c]; }); });
// row reverse
for (i in a){
a[i] = a[i].reverse();
}
return a;
}
Ruby-way: .transpose.map &:reverse
Tiempo - O (N), Espacio - O (1)
public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < n / 2; i++) {
int last = n - 1 - i;
for (int j = i; j < last; j++) {
int top = matrix[i][j];
matrix[i][j] = matrix[last - j][i];
matrix[last - j][i] = matrix[last][last - j];
matrix[last][last - j] = matrix[j][last];
matrix[j][last] = top;
}
}
}
Un par de personas ya han puesto ejemplos que implican hacer una nueva matriz.
Algunas otras cosas a considerar:
(a) En lugar de mover realmente los datos, simplemente atraviese la matriz "girada" de manera diferente.
(b) Hacer la rotación en el lugar puede ser un poco más complicado. Necesitarás un poco de espacio para rascar (probablemente más o menos igual al tamaño de una fila o columna). Hay un antiguo documento de ACM sobre cómo realizar transposiciones in situ ( http://doi.acm.org/10.1145/355719.355729 ), pero su código de ejemplo es desagradable y cargado de FORTRAN.
Apéndice:
http://doi.acm.org/10.1145/355611.355612 es otro algoritmo de transposición in situ supuestamente superior.
@dagorym: Aw, hombre. Me había aferrado a esto como un buen rompecabezas de "Me aburro, en qué puedo reflexionar". Encontré mi código de transposición en el lugar, pero llegué aquí para encontrar el tuyo casi idéntico al mío ... ah, bueno. Aquí está en Ruby.
require ''pp''
n = 10
a = []
n.times { a << (1..n).to_a }
pp a
0.upto(n/2-1) do |i|
i.upto(n-i-2) do |j|
tmp = a[i][j]
a[i][j] = a[n-j-1][i]
a[n-j-1][i] = a[n-i-1][n-j-1]
a[n-i-1][n-j-1] = a[j][n-i-1]
a[j][n-i-1] = tmp
end
end
pp a
Aquí hay un método de rotación en el espacio, por java, solo para el cuadrado. para una matriz 2d no cuadrada, tendrá que crear una nueva matriz de todos modos.
private void rotateInSpace(int[][] arr) {
int z = arr.length;
for (int i = 0; i < z / 2; i++) {
for (int j = 0; j < (z / 2 + z % 2); j++) {
int x = i, y = j;
int temp = arr[x][y];
for (int k = 0; k < 4; k++) {
int temptemp = arr[y][z - x - 1];
arr[y][z - x - 1] = temp;
temp = temptemp;
int tempX = y;
y = z - x - 1;
x = tempX;
}
}
}
}
código para rotar cualquier tamaño de matriz 2d creando una nueva matriz:
private int[][] rotate(int[][] arr) {
int width = arr[0].length;
int depth = arr.length;
int[][] re = new int[width][depth];
for (int i = 0; i < depth; i++) {
for (int j = 0; j < width; j++) {
re[j][depth - i - 1] = arr[i][j];
}
}
return re;
}
Puedes hacer esto en 3 sencillos pasos :
1 ) Supongamos que tenemos una matriz
1 2 3
4 5 6
7 8 9
2 ) Tomar la transposición de la matriz.
1 4 7
2 5 8
3 6 9
3 ) Intercambiar filas para obtener la matriz rotada.
3 6 9
2 5 8
1 4 7
Código fuente de Java para esto:
public class MyClass {
public static void main(String args[]) {
Demo obj = new Demo();
/*initial matrix to rotate*/
int[][] matrix = { { 1, 2, 3 }, { 4, 5, 6 }, { 7, 8, 9 } };
int[][] transpose = new int[3][3]; // matrix to store transpose
obj.display(matrix); // initial matrix
obj.rotate(matrix, transpose); // call rotate method
System.out.println();
obj.display(transpose); // display the rotated matix
}
}
class Demo {
public void rotate(int[][] mat, int[][] tran) {
/* First take the transpose of the matrix */
for (int i = 0; i < mat.length; i++) {
for (int j = 0; j < mat.length; j++) {
tran[i][j] = mat[j][i];
}
}
/*
* Interchange the rows of the transpose matrix to get rotated
* matrix
*/
for (int i = 0, j = tran.length - 1; i != j; i++, j--) {
for (int k = 0; k < tran.length; k++) {
swap(i, k, j, k, tran);
}
}
}
public void swap(int a, int b, int c, int d, int[][] arr) {
int temp = arr[a][b];
arr[a][b] = arr[c][d];
arr[c][d] = temp;
}
/* Method to display the matrix */
public void display(int[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr.length; j++) {
System.out.print(arr[i][j] + " ");
}
System.out.println();
}
}
}
Salida:
1 2 3
4 5 6
7 8 9
3 6 9
2 5 8
1 4 7
Ya hay muchas respuestas, y encontré dos que reclaman la complejidad del tiempo O (1). El algoritmo O (1) real es dejar el almacenamiento de la matriz sin tocar y cambiar la forma en que indexa sus elementos. El objetivo aquí es que no consume memoria adicional, ni requiere tiempo adicional para iterar los datos.
Las rotaciones de 90, -90 y 180 grados son transformaciones simples que se pueden realizar siempre que sepa cuántas filas y columnas hay en su matriz 2D; Para rotar cualquier vector en 90 grados, intercambie los ejes y niegue el eje Y. Para -90 grados, intercambia los ejes y niega el eje X. Para 180 grados, niega ambos ejes sin cambiar.
Son posibles otras transformaciones, como la duplicación horizontal y / o vertical mediante la negación de los ejes de forma independiente.
Esto se puede hacer a través de, por ejemplo, un método de acceso. Los siguientes ejemplos son funciones de JavaScript, pero los conceptos se aplican por igual a todos los idiomas.
// Get an array element in column/row order
var getArray2d = function(a, x, y) {
return a[y][x];
};
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 90 degrees clockwise
function getArray2dCW(a, x, y) {
var t = x;
x = y;
y = a.length - t - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2dCW(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 90 degrees counter-clockwise
function getArray2dCCW(a, x, y) {
var t = x;
x = a[0].length - y - 1;
y = t;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2dCCW(arr, i, j);
}
}
console.log(newarr);
// Get an array element rotated 180 degrees
function getArray2d180(a, x, y) {
x = a[0].length - x - 1;
y = a.length - y - 1;
return a[y][x];
}
//demo
var arr = [
[5, 4, 6],
[1, 7, 9],
[-2, 11, 0],
[8, 21, -3],
[3, -1, 2]
];
var newarr = [];
arr[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr.length; i++) {
for (var j = 0; j < newarr[0].length; j++) {
newarr[i][j] = getArray2d180(arr, i, j);
}
}
console.log(newarr);
Este código asume una matriz de matrices anidadas, donde cada matriz interna es una fila.
El método le permite leer (o escribir) elementos (incluso en orden aleatorio) como si la matriz se hubiera girado o transformado. Ahora solo elija la función correcta para llamar, probablemente por referencia, ¡y listo!
El concepto puede extenderse para aplicar transformaciones de forma aditiva (y no destructiva) a través de los métodos de acceso. Incluyendo rotaciones de ángulo arbitrario y escalado.
short normal[4][4] = {{8,4,7,5},{3,4,5,7},{9,5,5,6},{3,3,3,3}};
short rotated[4][4];
for (int r = 0; r < 4; ++r)
{
for (int c = 0; c < 4; ++c)
{
rotated[r][c] = normal[c][3-r];
}
}
Método simple de C ++, aunque habría una gran sobrecarga de memoria en una gran matriz.