在 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 转换为螺旋阵列

原文由 Smple_V 发布，翻译遵循 CC BY-SA 4.0 许可协议

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

原文由 jfs 发布，翻译遵循 CC BY-SA 3.0 许可协议

Answer 2

开场白

这个问题与以螺旋顺序打印数组的问题密切相关。事实上，如果我们已经有一个函数可以做到这一点，那么问题就相对简单了。

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

另一个原因是我发现的大多数生成螺旋矩阵的示例（包括问题和其他答案中的代码）仅处理大小为 nxn 的奇数 n 的方阵。在其他大小的矩阵中找到起点（或终点）可能很棘手。例如，对于 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 （其中 Ind = base_spiral(5,5) ）。

原文由 ptrj 发布，翻译遵循 CC BY-SA 3.0 许可协议