Solución:
Puede construir una espiral comenzando cerca del centro de la matriz y siempre girando a la derecha a menos que el elemento ya haya sido visitado:
#!/usr/bin/env python
NORTH, S, W, E = (0, -1), (0, 1), (-1, 0), (1, 0) # directions
turn_right = {NORTH: E, E: S, S: W, W: NORTH} # old -> new direction
def spiral(width, height):
if width < 1 or height < 1:
raise ValueError
x, y = width // 2, height // 2 # start near the center
dx, dy = NORTH # initial direction
matrix = [[None] * width for _ in range(height)]
count = 0
while True:
count += 1
matrix[y][x] = count # visit
# try to turn right
new_dx, new_dy = turn_right[dx,dy]
new_x, new_y = x + new_dx, y + new_dy
if (0 <= new_x < width and 0 <= new_y < height and
matrix[new_y][new_x] is None): # can turn right
x, y = new_x, new_y
dx, dy = new_dx, new_dy
else: # try to move straight
x, y = x + dx, y + dy
if not (0 <= x < width and 0 <= y < height):
return matrix # nowhere to go
def print_matrix(matrix):
width = len(str(max(el for row in matrix for el in row if el is not None)))
fmt = "{:0%dd}" % width
for row in matrix:
print(" ".join("_"*width if el is None else fmt.format(el) for el in row))
Ejemplo:
>>> print_matrix(spiral(5, 5))
21 22 23 24 25
20 07 08 09 10
19 06 01 02 11
18 05 04 03 12
17 16 15 14 13
Notas introductorias
La pregunta está estrechamente relacionada con el problema de imprimir una matriz en orden en espiral. De hecho, si ya tenemos una función que lo hace, entonces el problema en cuestión es relativamente simple.
Hay una multitud de recursos sobre cómo producir una matriz en espiral o cómo hacer un bucle o imprimir una matriz en orden en espiral. Aun así, decidí escribir mi propia versión, usando matrices numpy. La idea no es original, pero el uso de numpy hace que el código sea más conciso.
La otra razón es que la mayoría de los ejemplos de producción de una matriz en espiral que encontré (incluido el código en la pregunta y en las otras respuestas) tratan solo con matrices cuadradas de tamaño nxn para n impares. Encontrar el punto inicial (o final) en matrices de otros tamaños puede resultar complicado. Por ejemplo, para una matriz de 3×5, no puede ser la celda del medio. El siguiente código es general y la posición del punto inicial (final) depende de la elección de la función spiral_xxx.
Código
La primera función desenvuelve una matriz en orden de espiral en el sentido de las agujas del reloj:
import numpy as np
def spiral_cw(A):
A = np.array(A)
out = []
while(A.size):
out.append(A[0]) # take first row
A = A[1:].T[::-1] # cut off first row and rotate counterclockwise
return np.concatenate(out)
Podemos escribir esta función de ocho formas diferentes dependiendo de dónde empecemos y cómo rotamos la matriz. Daré otro, que es consistente (será evidente más adelante) con la transformación matricial en la imagen de la pregunta. Entonces, más adelante, usaré esta versión:
def spiral_ccw(A):
A = np.array(A)
out = []
while(A.size):
out.append(A[0][::-1]) # first row reversed
A = A[1:][::-1].T # cut off first row and rotate clockwise
return np.concatenate(out)
Cómo funciona:
A = np.arange(15).reshape(3,5)
print(A)
[[ 0 1 2 3 4]
[ 5 6 7 8 9]
[10 11 12 13 14]]
print(spiral_ccw(A))
[ 4 3 2 1 0 5 10 11 12 13 14 9 8 7 6]
Tenga en cuenta que el punto final (o inicio) no es la celda del medio. Esta función funciona para todo tipo de matrices pero necesitaremos una función auxiliar que genere índices espirales:
def base_spiral(nrow, ncol):
return spiral_ccw(np.arange(nrow*ncol).reshape(nrow,ncol))[::-1]
Por ejemplo:
print(base_spiral(3,5))
[ 6 7 8 9 14 13 12 11 10 5 0 1 2 3 4]
Ahora vienen los dos funciones principales. Uno transforma una matriz en una forma de espiral de las mismas dimensiones, el otro revierte la transformación:
def to_spiral(A):
A = np.array(A)
B = np.empty_like(A)
B.flat[base_spiral(*A.shape)] = A.flat
return B
def from_spiral(A):
A = np.array(A)
return A.flat[base_spiral(*A.shape)].reshape(A.shape)
Ejemplos de
Matriz 3 x 5:
A = np.arange(15).reshape(3,5)
print(A)
[[ 0 1 2 3 4]
[ 5 6 7 8 9]
[10 11 12 13 14]]
print(to_spiral(A))
[[10 11 12 13 14]
[ 9 0 1 2 3]
[ 8 7 6 5 4]]
print(from_spiral(to_spiral(A)))
[[ 0 1 2 3 4]
[ 5 6 7 8 9]
[10 11 12 13 14]]
Matriz de la pregunta:
B = np.arange(1,26).reshape(5,5)
print(B)
[[ 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]]
print(to_spiral(B))
[[21 22 23 24 25]
[20 7 8 9 10]
[19 6 1 2 11]
[18 5 4 3 12]
[17 16 15 14 13]]
print(from_spiral(to_spiral(B)))
[[ 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]]
Observación
Si va a trabajar solo con matrices de tamaño fijo, por ejemplo 5×5, entonces vale la pena reemplazarlas base_spiral(*A.shape) en las definiciones de las funciones con una matriz fija de índices, digamos Ind (dónde Ind = base_spiral(5,5)).
Aquí hay una solución usando itertools y prácticamente nada de matemáticas, solo observaciones sobre el aspecto de la espiral. Creo que es elegante y bastante fácil de entender.
from math import ceil, sqrt
from itertools import cycle, count, izip
def spiral_distances():
"""
Yields 1, 1, 2, 2, 3, 3, ...
"""
for distance in count(1):
for _ in (0, 1):
yield distance
def clockwise_directions():
"""
Yields right, down, left, up, right, down, left, up, right, ...
"""
left = (-1, 0)
right = (1, 0)
up = (0, -1)
down = (0, 1)
return cycle((right, down, left, up))
def spiral_movements():
"""
Yields each individual movement to make a spiral:
right, down, left, left, up, up, right, right, right, down, down, down, ...
"""
for distance, direction in izip(spiral_distances(), clockwise_directions()):
for _ in range(distance):
yield direction
def square(width):
"""
Returns a width x width 2D list filled with Nones
"""
return [[None] * width for _ in range(width)]
def spiral(inp):
width = int(ceil(sqrt(len(inp))))
result = square(width)
x = width // 2
y = width // 2
for value, movement in izip(inp, spiral_movements()):
result[y][x] = value
dx, dy = movement
x += dx
y += dy
return result
Uso:
from pprint import pprint
pprint(spiral(range(1, 26)))
Producción:
[[21, 22, 23, 24, 25],
[20, 7, 8, 9, 10],
[19, 6, 1, 2, 11],
[18, 5, 4, 3, 12],
[17, 16, 15, 14, 13]]
Aquí está la misma solución abreviada:
def stretch(items, counts):
for item, count in izip(items, counts):
for _ in range(count):
yield item
def spiral(inp):
width = int(ceil(sqrt(len(inp))))
result = [[None] * width for _ in range(width)]
x = width // 2
y = width // 2
for value, (dx, dy) in izip(inp,
stretch(cycle([(1, 0), (0, 1), (-1, 0), (0, -1)]),
stretch(count(1),
repeat(2)))):
result[y][x] = value
x += dx
y += dy
return result
He ignorado el hecho de que desea que la entrada sea una matriz 2D, ya que tiene mucho más sentido que sea cualquier iterable 1D. Puede aplanar fácilmente la matriz 2D de entrada si lo desea. También asumí que la salida debería ser un cuadrado, ya que no puedo pensar en lo que querrías de otra manera. Puede sobrepasar el límite y generar un error si el cuadrado tiene una longitud uniforme y la entrada es demasiado larga: de nuevo, no sé cuál sería la alternativa.