Cómo hacer girar una matriz bidimensional?
https://stackoverflow.com/questions/42519
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Inspirado por Raymond Chen post, digamos que tienes un 4x4 de dos dimensiones de la matriz, escribir una función que gira en 90 grados.Raymond enlaces a una solución en pseudo-código, pero me gustaría ver algo de mundo real de las cosas.
[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:Nick respuesta es la más sencilla, pero hay una manera de hacerlo mejor que n^2?¿Qué pasa si la matriz fue 10000x10000?
Solución
Aquí es 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;
}
Otros consejos
O(n^2) tiempo y O(1) espacio de algoritmo ( sin ningún tipo de soluciones y de hanky-panky cosas!)
Rotar +90:
- Transponer
- Inversa de cada fila
Gire -90:
Método 1 :
- Transponer
- Inversa de cada columna
Método 2 :
- Inversa de cada fila
- Transponer
Rotar +180:
Método 1:Rotar +90 dos veces
Método 2:Inversa de cada fila y, a continuación, invertir cada columna (Transpose)
Rotar por -180:
Método 1:Gire -90 dos veces
Método 2:Inversa de cada columna y, a continuación, invertir cada fila
Método 3:Rotar +180 como no son lo mismo
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 que se ofrece aquí no es la más sintácticamente compacta, es sin embargo, para aquellos que quieran conocer la matriz de rotación y la implementación resultante.
En primer lugar, qué es una matriz?Para los efectos de esta respuesta, una matriz es simplemente una cuadrícula donde la anchura y la altura es la misma.Nota, la anchura y la altura de una matriz pueden ser diferentes, pero por razones de simplicidad, este tutorial solo considera las matrices con la misma anchura y altura (las matrices cuadradas).Y sí, matrices es el plural de la matriz.
Ejemplo de matrices son:2×2, 3×3 o 5×5.O, más en general, de N×N.Un 2×2 de la matriz de 4 plazas porque 2×2=4.Una matriz 5×5 tendrá 25 plazas porque 5×5=25.Cada cuadrado se llama un elemento o entrada.Vamos a representar cada elemento con un período (.) en los diagramas de abajo:
2×2 de la matriz
. .
. .
3×3 de la matriz
. . .
. . .
. . .
4×4 de la matriz
. . . .
. . . .
. . . .
. . . .
Así que, ¿qué significa para girar una matriz?Echemos un 2×2 de la matriz y poner algunos números en cada elemento para que la rotación se puede observar:
0 1
2 3
Rotación de este 90 grados nos da:
2 0
3 1
Nos convirtió, literalmente, toda la matriz de una vez a la derecha como a girar el volante de un coche.Esto puede ayudar a pensar en la "propina" de la matriz en su lado derecho.Queremos escribir una función en Python, que toma una matriz y gira en una vez a la derecha.La función de la firma será:
def rotate(matrix):
# Algorithm goes here.
La matriz se define mediante una matriz de dos dimensiones:
matrix = [
[0,1],
[2,3]
]
Por lo tanto, el primer índice de la posición de los accesos de la fila.El segundo índice de la posición de los accesos de la columna:
matrix[row][column]
Vamos a definir una función de utilidad para imprimir una matriz.
def print_matrix(matrix):
for row in matrix:
print row
Un método de rotación de una matriz es hacerlo de una capa a la vez.Pero, ¿qué es una capa?Creo que de una cebolla.Al igual que las capas de una cebolla, ya que cada capa es removida, nos movemos hacia el centro.Otras analogías es una Matryoshka muñeca o un juego de pasar a la parcela.
La anchura y la altura de una matriz de dictar el número de capas en que la matriz.Vamos a utilizar símbolos diferentes para cada capa:
Un 2×2 matriz de 1 capa
. .
. .
Un 3×3 matriz tiene 2 capas
. . .
. x .
. . .
Un 4×4 de la matriz tiene 2 capas
. . . .
. x x .
. x x .
. . . .
Una matriz 5×5 tiene 3 capas
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Un 6×6 matriz tiene 3 capas
. . . . . .
. x x x x .
. x O O x .
. x O O x .
. x x x x .
. . . . . .
Un 7×7 matriz 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 .
. . . . . . .
Usted puede notar que el incremento de la anchura y la altura de una matriz por uno, no siempre aumentar el número de capas.Toma las matrices y tablas de las capas y dimensiones, vemos que el número de capas aumenta una vez por cada dos incrementos de anchura y altura:
+-----+--------+
| 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 de la necesidad de rotar.Un 1×1 de la matriz es la misma antes y después de la rotación.La central de 1×1 de la capa siempre es la misma antes y después de la rotación, no importa cuán grande sea el total de la matriz:
+-----+--------+------------------+
| 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 |
+-----+--------+------------------+
Dado N×N matriz, ¿cómo podemos determinar mediante programación el número de capas que necesitamos para girar?Si dividimos el ancho o el alto por dos y omitir 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 |
+-----+--------+------------------+---------+
Observe cómo N/2 coincide con el número de capas que deben ser girado?A veces, el número de giratorio en capas es uno menos que 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,un 1×1 de la matriz) y por lo tanto no necesita ser girado.Simplemente se ignora.
Sin duda nos necesita esta información en nuestra función para girar una matriz, así que vamos a añadir ahora:
def rotate(matrix):
size = len(matrix)
# Rotatable layers only.
layer_count = size / 2
Ahora sabemos lo que las capas son y cómo determinar el número de capas que realmente necesitan de rotación, ¿cómo podemos aislar una sola capa, de manera que podemos girar?En primer lugar, examinamos una matriz a partir de la capa más externa, hacia adentro, de la capa más interna.Una matriz 5×5 tiene tres capas en total y dos capas que necesitan de rotación:
. . . . .
. x x x .
. x O x .
. x x x .
. . . . .
Echemos un vistazo a las columnas de la primera.La posición de las columnas que definen la capa más externa, asumiendo que contamos desde 0, 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 siempre será el caso, ya que la anchura y la altura es la misma.Por lo tanto, podemos definir la columna y la fila posiciones de una capa con sólo dos valores (en lugar de cuatro).
Hacia adentro a la segunda capa, la posición de las columnas 1 y 3.Y, sí, lo has adivinado, es el mismo para las filas.Es importante entender que teníamos para incrementar y disminuir las posiciones de fila y columna cuando se mueve hacia adentro 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 |
+-----------+---------+---------+---------+
Así, para la inspección de cada capa, queremos un bucle con el aumento y la disminución de los contadores que representan hacia adentro, a partir de la capa más externa.Vamos a llamar a esta nuestra capa de "ciclo".
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 de arriba bucles a través de la (fila y columna) posiciones de las capas que la necesidad de rotar.
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 identificar la posición de índice de la primera y última filas y columnas.Refiriéndose de nuevo a nuestra fila y columna de las tablas:
+--------+-----------+
| 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 | . . . . . |
+-----+-----------+
Por lo que se puede navegar a través de las capas de una matriz.Ahora tenemos una forma de navegar dentro de una capa para que podamos mover elementos en torno a esa capa.Nota, elementos nunca "saltar" de una capa a otra, pero se mueve dentro de sus respectivas capas.
Rotación de cada elemento en una capa gira toda la capa.Rotación de todas las capas en una matriz a la que gira toda la matriz.Esta frase es muy importante, así que por favor intente su mejor para entender esto antes de continuar.
Ahora, necesitamos una forma de realidad, el movimiento de los elementos, es decir,gire cada elemento, y posteriormente la capa, y en última instancia de la matriz.Por simplicidad, vamos a volver a una matriz de 3x3 — que tiene una giratorio de la capa.
0 1 2
3 4 5
6 7 8
Nuestra capa de bucle proporciona los índices de la primera y última columnas, así como la primera y la última fila:
+-----+-------+
| 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 |
+-----+-------+
Porque nuestras matrices son siempre de la plaza, necesitamos sólo dos variables, first y last, desde las posiciones de índice son los mismos para las 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 de primer y el último puede ser fácilmente utilizado para hacer referencia a las cuatro esquinas de una matriz.Esto es debido a que las esquinas pueden ser definidos usando varias permutaciones de first y last (con no resta, suma o desplazamiento de las 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 el exterior de las cuatro esquinas — vamos a rotar los primeros.Vamos a poner de relieve con *.
* 1 *
3 4 5
* 7 *
Queremos intercambiar * con el * a la derecha de ella.Así que vamos a ir por delante de imprimir nuestros rincones define con sólo varias permutaciones de first y 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 nos podría muy fácilmente swap de cada uno de los rincones de nuestra capa de bucle:
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)
La matriz antes de girar las esquinas:
[0, 1, 2]
[3, 4, 5]
[6, 7, 8]
De la matriz después de la rotación de las esquinas:
[6, 1, 0]
[3, 4, 5]
[8, 7, 2]
Genial!!!Hemos logrado girar 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 lazo en nuestra función (a lo largo de nuestra capa de bucle), pasa a la siguiente capa en cada iteración.Desde nuestra matriz sólo tiene un giratorio de la capa, la capa de bucle termina después de girar sólo en las esquinas.Echemos un vistazo a lo que sucede con una más grande, la matriz 5×5 (donde dos capas necesidad de rotación).El código de la función que 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)
El resultado 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 ser una sorpresa que las esquinas de la capa más externa se han girado, pero, también puede observar las esquinas de la siguiente capa (hacia adentro) también han sido girado.Esto tiene sentido.Hemos escrito código para navegar a través de capas y también para girar las esquinas de cada capa.Esto se siente como un progreso, pero por desgracia tenemos que dar un paso atrás.Es sólo no es bueno pasar a la siguiente capa hasta que la anterior (exterior) de la capa ha sido completamente girado.Es decir, hasta que cada elemento en la capa ha sido girado.Rotación sólo las esquinas no!
Tome una respiración profunda.Necesitamos otro bucle.Un bucle anidado no menos.El nuevo bucle anidado, se utilizará el first y last variables, además de un desplazamiento para navegar dentro de una capa.Vamos a llamar a este nuevo bucle de nuestro " elemento de circuito.El elemento bucle se visita cada elemento a lo largo de la fila superior, de cada elemento por el lado derecho, cada elemento a lo largo de la parte inferior de la fila y de cada elemento hasta el lado izquierdo.
- Moviéndose hacia adelante, a lo largo de la fila superior requiere de la columna el índice se incrementa.
- Mover hacia abajo el lado derecho requiere que el índice de fila para ser incrementa.
- Se mueve hacia atrás a lo largo de la parte inferior requiere de la columna índice disminuye.
- Moviéndose hacia la izquierda requiere el índice de fila para ser decrementa.
Esto suena complicado, pero es fácil debido a que el número de veces que nos de incremento y decremento para alcanzar el anterior sigue siendo el mismo a lo largo de los cuatro lados de la matriz.Por ejemplo:
- Mover 1 elemento en la fila superior.
- Mover 1 elemento por el lado derecho.
- Mover 1 elemento hacia atrás a lo largo de la fila inferior.
- Mover 1 elemento hasta el lado izquierdo.
Esto significa que se puede utilizar una sola variable en combinación con el first y last las variables que se mueven dentro de una capa.Puede ayudar a la nota que se mueve a través de la fila de arriba y abajo del lado derecho tanto requieren incrementar.Mientras se mueve hacia atrás a lo largo de la parte inferior y el lado izquierdo ambos requieren decrecer.
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 tenemos que asignar la parte superior a la derecha, el lado derecho de la parte inferior, la parte inferior a la izquierda, y el lado izquierdo de la parte superior.Poniendo todo esto junto, se obtiene:
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
Nuestro rotate resultados en función de:
6, 3, 0
7, 4, 1
8, 5, 2
Python:
rotated = zip(*original[::-1]) # On Python 3, list(zip(*original[::-1]))
Barato, lo sé.
Y en el sentido contrario:
rotated_ccw = zip(*original)[::-1] # On Python 3, list(zip(*original))[::-1]
Cómo funciona esto: (Se solicita en los comentarios)
zip(*original) intercambio ejes de 2d matrices por el apilamiento de los elementos correspondientes de las listas en las nuevas listas.(El * el operador le dice a la función de distribuir los contenidos en las listas de argumentos)
>>> zip(*[[1,2,3],[4,5,6],[7,8,9]])
[[1,4,7],[2,5,8],[3,6,9]]
El [::-1] declaración invierte los elementos de la matriz (por favor, ver Extendido Rodajas).
>>> [[1,2,3],[4,5,6],[7,8,9]][::-1]
[[7,8,9],[4,5,6],[1,2,3]]
Finalmente, la combinación de los dos será el resultado de la rotación de la transformación.
El cambio en la colocación de [::-1] invertir listas en diferentes niveles de la matriz.
Aquí es que se hace la rotación en lugar en lugar de utilizar una completamente nueva matriz para mantener el resultado.Yo he dejado de inicialización de la matriz y de imprimir.Esto funciona sólo para matrices cuadradas, pero pueden ser de cualquier tamaño.Sobrecarga de la memoria es igual al tamaño de un elemento de la matriz por lo que usted puede hacer la rotación de tan grande una matriz como usted desea.
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;
}
}
Hay un montón de buenas aquí el código, pero solo quiero mostrar lo que está pasando en geométricamente así que usted puede entender la lógica de código un poco mejor.Aquí es cómo iba a acercarse a este.
primero de todo, no hay que confundir esto con la transposición que es muy fácil..
la idea basica es tratarlo como capas y lo hacemos girar 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 girar a la derecha por 90 obtenemos
13 9 5 1
14 10 6 2
15 11 7 3
16 12 8 4
así que vamos a descomponer este, en primer lugar hemos de girar a los 4 rincones esencialmente
1 4
13 16
luego se rota el siguiente diamante que es una especie de rara
2
8
9
15
y luego la 2ª sesgada de diamante
3
5
12
14
así que cuida del borde exterior así que, esencialmente, hacemos que una shell en un momento hasta que
finalmente el medio de la plaza (o si es impar sólo el último elemento que no se mueve)
6 7
10 11
así que ahora vamos a averiguar los índices de cada capa, asumir siempre trabajamos con la capa más externa, que 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]
y así sucesivamente hasta que estamos a mitad de 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]
Como dije en mi anterior post, aquí un poco de código en C# que implementa una operación O(1) de la matriz de rotación para cualquier tamaño de la matriz.En aras de la brevedad y la legibilidad no hay ninguna comprobación de errores, o intervalo de comprobación.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;
}
OK, voy a poner mi mano, que en realidad no hace ninguna modificación a la matriz original al girar.Pero, en un sistema OO eso no importa, siempre que el objeto parece haber sido girado a los clientes de la clase.Por el momento, la clase Matrix utiliza referencias a la matriz original de datos, de modo de cambiar cualquier valor de m1 también va a cambiar, m2 y m3.Un pequeño cambio en el constructor para crear una nueva matriz y la copia de los valores a ordenar que fuera.
Mientras que la rotación de los datos en su lugar podría ser necesario (tal vez para actualizar la almacenada físicamente la representación), se vuelve más simple y posiblemente más eficientes para agregar una capa de indirección en el acceso a una matriz, tal vez una interfaz:
interface IReadableMatrix
{
int GetValue(int x, int y);
}
Si su Matrix ya implementa esta interfaz, a continuación, se puede girar a través de un decorador la clase 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);
}
}
Rotación +90/-90/180 grados, voltear horizontalmente/verticalmente y la escala se puede hacer todo en esta moda.
El rendimiento de la necesidad de ser medido en su situación específica.Sin embargo, el O(n^2) operación ha sido reemplazado con un O(1) de la llamada.Es un método virtual llamada que es más lento que el directo de acceso a una matriz, por lo que depende de la frecuencia con la que rotados matriz se usa después de la rotación.Si se utiliza una vez, este enfoque sería, sin duda ganar.Si se gira utilizado en un sistema de ejecución prolongada de días, entonces en lugar de la rotación puede funcionar mejor.También depende de si usted puede aceptar el costo por adelantado.
Como con todos los problemas de rendimiento, medir, medir, medir!
Esta mejor la versión en Java:Yo la he hecho para una matriz con distinta anchura y altura
- h es aquí la altura de la matriz después de rotar
- w es aquí el ancho de la matriz después de rotar
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 está basado en el Nick Berardi del post.
Ruby-forma: .transpose.map &:reverse
Hay un montón de respuestas ya, y he encontrado dos reclamar O(1) tiempo de complejidad.El real O(1) el algoritmo es dejar el almacenamiento de la matriz de virgen, y cambiar la forma de índice de sus elementos.El objetivo aquí es que no consume memoria adicional, ni requiere tiempo adicional para recorrer los datos.
Rotaciones de 90, - 90 y 180 grados son simples transformaciones que se pueden realizar siempre y cuando usted sabe cuántas filas y columnas en la matriz 2D;Para girar cualquier vector de 90 grados, cambiar los ejes y negar el eje Y.Para -90 grados, cambiar los ejes y negar el eje X.De 180 grados, negar ambos ejes sin necesidad de cambiar.
Más transformaciones son posibles, tales como la creación de reflejo horizontal y/o verticalmente mediante la negación de los ejes de forma independiente.
Esto se puede hacer a través, por ejemplo,un método de descriptor de acceso.Los ejemplos siguientes son las 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[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = 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[0].forEach(() => newarr.push(new Array(arr.length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = 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.forEach(() => newarr.push(new Array(arr[0].length)));
for (var i = 0; i < newarr[0].length; i++) {
for (var j = 0; j < newarr.length; j++) {
newarr[j][i] = getArray2d180(arr, i, j);
}
}
console.log(newarr);Este código supone una matriz de matrices anidadas, donde cada interno matriz de una fila.
El método permite leer (o escribir) de los elementos (incluso en orden aleatorio) como si la matriz ha sido rotado o transformado.Ahora acaba de elegir el derecho de la función a llamar, probablemente por referencia, y listo!
El concepto puede ser extendido para aplicar transformaciones de forma aditiva (y no destructiva) a través de los métodos de descriptor de acceso.Incluyendo arbitraria ángulo de rotación y escalado.
Un par de personas que ya hay ejemplos que implican la realización de una nueva matriz.
Algunas otras cosas a considerar:
(a) en Lugar de en realidad el movimiento de los datos, simplemente atravesar el "girado" matriz de manera diferente.
(b) Hacer la rotación en el lugar puede ser un poco complicado.Vas a necesitar un poco de scratch lugar (probablemente casi igual a la de una fila o columna en tamaño).Hay un antiguo ACM papel haciendo en el lugar transpone (http://doi.acm.org/10.1145/355719.355729), pero su ejemplo de código es desagradable ir cargados de FORTRAN.
Addendum:
http://doi.acm.org/10.1145/355611.355612 es otro, supuestamente superior, en lugar de transponer algoritmo.
Nick respuesta funcionaría para una matriz NxM con sólo una pequeña modificación (como opuesto a un 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 manera de pensar acerca de esto es que usted se ha mudado al centro del eje (0,0) de la esquina superior izquierda a la esquina superior derecha.Simplemente eres la transposición de uno a otro.
Tiempo O(N), El 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;
}
}
}
Aquí está mi versión de Ruby (nota: los valores no se muestran de la misma, pero todavía 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))
El resultado:
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
aquí está una en el espacio-método rotate, java, sólo para la plaza.para los no-plaza matriz 2d, 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 girar cualquier tamaño de matriz 2d mediante la creación de la 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;
}
La implementación de hoyuelo de +90 pseudocódigo (por ejemplo,la transposición, a continuación, invertir 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;
}
Usted puede hacer esto en 3 pasos fáciles:
1)Supongamos que tenemos una matriz de
1 2 3
4 5 6
7 8 9
2)Tomar la transpuesta de la matriz
1 4 7
2 5 8
3 6 9
3)El intercambio de filas para obtener de la matriz rotada
3 6 9
2 5 8
1 4 7
Java código fuente 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
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);
}
}
?>
Esta es mi aplicación, en C, O(1) memoria de la complejidad, en lugar de la rotación de 90 grados a la derecha:
#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;
}
}
}
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 primer método gire el mostouter capa, a continuación, pasar a la capa interior squentially.
A partir de un lineal de punto de vista, considere las matrices:
1 2 3 0 0 1
A = 4 5 6 B = 0 1 0
7 8 9 1 0 0
Ahora tome Una transposición de
1 4 7
A' = 2 5 8
3 6 9
Y considerar la acción de Un' en B, o de 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 extensible para cualquier n x n de la matriz.Y la aplicación de 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);
}
}
}
Código de C# para girar [n,m] 2D matrices de 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
For i:= 0 to X do
For j := 0 to X do
graphic[j][i] := graphic2[X-i][j]
X es el tamaño de la matriz de la gráfica es en.
#transposición es un método estándar de Ruby de la clase Array, 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 aplicación es un n^2 función de transposición escrito en C.Usted puede ver aquí:http://www.ruby-doc.org/core-1.9.3/Array.html#method-i-transpose por la elección de "haga clic para alternar la fuente" al lado de "transponer".
Recuerdo mejor que O(n^2) soluciones, pero sólo para la construcción especial de las matrices (tales como matrices dispersas)
C código de la matriz de rotación de 90 grados en sentido horario EN el LUGAR para cualquier M*N de la matriz
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;
}
}
}
aquí está mi En Lugar de la implementación 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 la matriz de 90 grados de rotación que es un 2 solución paso en C.Primero la transposición de la matriz en su lugar y, a continuación, intercambiar las cols.
#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;
}
@dagorym:Aw, hombre.Yo había estado colgando en el este como un buen "estoy aburrido, ¿qué puedo reflexionar sobre" puzzle.Se me ocurrió a mi en lugar de transposición de código, pero llegué aquí para encontrar la suya casi idéntica a la mía...ah, bien.Aquí es 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
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];
}
}
Simple método de C++, aunque no sería una gran sobrecarga de la memoria en una gran variedad.
