creando una matriz en espiral en python?

Mi compañero y yo intentábamos crear un juego divertido en Python donde se accede a los elementos ingresados ​​en la matriz de forma espiral. He intentado algunos métodos como uno dado a continuación ( fuente ).

def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y)**2): if (-X/2 < x <= X/2) and (-Y/2 < y <= Y/2): print (x, y) # DO STUFF... if x == y or (x  0 and x == 1-y): dx, dy = -dy, dx x, y = x+dx, y+dy 

La statement anterior accede a los elementos en espiral y los imprime para una matriz definida AE. Me gustaría saber cómo puedo transformar una matriz dada AE en una espiral

Array AE

Puedes 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 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 espiral o cómo hacer un bucle o imprimir una matriz en orden 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 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 impar. Encontrar el punto inicial (o final) en matrices de otros tamaños puede ser complicado. Por ejemplo, para una matriz de 3×5 no puede ser la celda central. 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 espiral en sentido horario:

 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 en ocho formas diferentes dependiendo de dónde comencemos y de cómo giremos la matriz. Daré otro, que es consistente (será evidente más adelante) con la transformación de la matriz en la imagen de la pregunta. Así que, 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 central. Esta función funciona para todo tipo de matrices, pero necesitaremos una función auxiliar que genere índices en espiral :

 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 las dos funciones principales . Uno transforma una matriz en una forma 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

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 reemplazar base_spiral(*A.shape) en las definiciones de las funciones con una matriz fija de índices, digamos Ind (donde Ind = base_spiral(5,5) ).

Aquí hay una solución que usa itertools y prácticamente no matemática, solo observaciones acerca de cómo se ve 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))) 

Salida:

 [[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í se acorta la misma solución:

 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 una iterable en 1D. Si lo desea, puede aplanar fácilmente la matriz de entrada 2D. También asumí que la salida debería ser cuadrada, ya que no puedo pensar lo que de otra forma sería sensato. Puede ir más allá del borde y generar un error si el cuadrado tiene una longitud uniforme y la entrada es demasiado larga: una vez más, no sé cuál sería la alternativa.

A continuación se muestra el código python3 que transforma:

  [[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]] 

a

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

Puede cambiar fácilmente la implementación de tal manera, cómo quiere …

  def spiral(X, Y): x = y = 0 dx = 0 dy = -1 for i in range(max(X, Y) ** 2): if (-X / 2 < x <= X / 2) and (-Y / 2 < y <= Y / 2): yield x, y # print(x, y) # DO STUFF... if x == y or (x < 0 and x == -y) or (x > 0 and x == 1 - y): dx, dy = -dy, dx x, y = x + dx, y + dy spiral_matrix_size = 5 my_list = list(range(spiral_matrix_size**2)) my_list = [my_list[x:x + spiral_matrix_size] for x in range(0, len(my_list), spiral_matrix_size)] print(my_list) for i, (x, y) in enumerate(spiral(spiral_matrix_size, spiral_matrix_size)): diff = int(spiral_matrix_size / 2) my_list[x + diff][y + diff] = i print(my_list) 

Puedes llenar una matriz con algo como esto:

 #!/usr/bin/python class filler: def __init__(self, srcarray): self.size = len(srcarray) self.array = [[None for y in range(self.size)] for y in range(self.size)] self.xpos, self.ypos = 0, 0 self.directions = [self.down, self.right, self.up, self.left] self.direction = 0 self.fill(srcarray) def fill(self, srcarray): for row in reversed(srcarray): for elem in reversed(row): self.array[self.xpos][self.ypos] = elem self.go_to_next() def check_next_pos(self): np = self.get_next_pos() if np[1] in range(self.size) and np[0] in range(self.size): return self.array[np[0]][np[1]] == None return False def go_to_next(self): i = 0 while not self.check_next_pos() and i < 4: self.direction = (self.direction + 1) % 4 i += 4 self.xpos, self.ypos = self.get_next_pos() def get_next_pos(self): return self.directions[self.direction](self.xpos, self.ypos) def down(self, x, y): return x + 1, y def right(self, x, y): return x, y + 1 def up(self, x, y): return x - 1, y def left(self, x, y): return x, y - 1 def print_grid(self): for row in self.array: print(row) f = filler([[x+y*5 for x in range(5)] for y in range(5)]) f.print_grid() 

El resultado de esto será:

 [24, 9, 10, 11, 12] [23, 8, 1, 2, 13] [22, 7, 0, 3, 14] [21, 6, 5, 4, 15] [20, 19, 18, 17, 16] 
 def counter(n): for i in range(1,n*n): yield i+1 n = 11 a = [[1 for x in range(n)] for y in range(n)] x = y = n//2 val = counter(n) for i in range(2, n, 2): y += 1 x -= 1 for k in range(i): x += 1 a[x][y] = next(val) for k in range(i): y -= 1 a[x][y] = next(val) for k in range(i): x -= 1 a[x][y] = next(val) for k in range(i): y += 1 a[x][y] = next(val) for i in range(n): for j in range(n): print (a[i][j] , end="") print (" " , end="") print("\n")