在python中创建一个螺旋数组？

Question

我和我的伙伴正试图在python中创建一个有趣的游戏,其中输入数组的元素以螺旋方式访问.我尝试过几种方法,例如下面给出的方法(来源).

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 == -y) or (x > 0 and x == 1-y):
        dx, dy = -dy, dx
    x, y = x+dx, y+dy

上面的语句访问螺旋循环中的元素,并为定义的数组AE打印它们.我想知道如何将给定的阵列AE转换为螺旋阵列

Answer 1

您可以通过在矩阵中心附近开始构建螺旋线,并始终向右转,除非已经访问过该元素:

#!/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))

例:

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

Answer 2

介绍性发言

该问题与以螺旋顺序打印阵列的问题密切相关.事实上,如果我们已经有了一个功能,那么问题就相对简单了.

关于如何生成螺旋矩阵或如何以螺旋顺序循环或打印阵列有很多资源.即便如此,我决定使用numpy数组编写自己的版本.这个想法不是原创的,但使用numpy会使代码更简洁.

另一个原因是,我发现的大多数产生螺旋矩阵的例子(包括问题和其他答案中的代码)仅涉及奇数n的大小为nxn的平方矩阵.在其他尺寸的矩阵中找到起点(或终点)可能很棘手.例如,对于3x5矩阵,它不能是中间单元.下面的代码是通用的,起始(结束)点的位置取决于函数的选择spiral_xxx.

码

第一个函数以顺时针螺旋顺序展开数组:

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)

我们可以根据我们开始的位置以及如何旋转矩阵,以八种不同的方式编写此函数.我将给出另一个与问题中的图像中的矩阵变换一致的(后面将会很明显).所以,进一步说,我将使用这个版本:

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)

这个怎么运作:

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]

请注意,结束(或开始)点不是中间单元格.此函数适用于所有类型的矩阵,但我们需要一个生成螺旋索引的辅助函数:

def base_spiral(nrow, ncol):
    return spiral_ccw(np.arange(nrow*ncol).reshape(nrow,ncol))[::-1]

例如:

print(base_spiral(3,5))
[ 6  7  8  9 14 13 12 11 10  5  0  1  2  3  4]

现在来看两个主要功能.一个将矩阵转换为相同维度的螺旋形式,另一个转换为转换:

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)

例子

矩阵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]]

来自问题的矩阵:

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

备注

如果你只打算使用固定大小的矩阵,例如5x5,那么base_spiral(*A.shape)用固定的索引矩阵代替函数定义,比如说Ind(where Ind = base_spiral(5,5)).