在python中创建螺旋数组？

Question

我和我的伙伴试图用python创建一个有趣的游戏，其中数组中输入的元素以螺旋方式访问。我尝试过一些方法，比如下面给出的方法（source）。

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

导言

这个问题与按螺旋顺序打印阵列的问题密切相关。事实上，如果我们已经有一个函数来完成它，那么问题就相对简单了。

在how to produce a spiral matrix或如何loop或print按螺旋顺序排列数组上有大量资源。即便如此，我还是决定用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（其中Ind = base_spiral(5,5)）。

Answer 3

这里有一个使用itertools的解决方案，实际上没有数学，只是观察螺旋的样子。我觉得很优雅，也很容易理解。

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

用法：

from pprint import pprint
pprint(spiral(range(1, 26)))

输出：

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

下面是同样的解决方案：

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

我忽略了一个事实，你希望输入是一个2D数组，因为它对于任何1D的iterable都更有意义。如果需要，可以轻松地展平输入的二维数组。我也假设输出应该是平方的，因为我想不出你会想要什么。如果正方形的长度相等，而且输入的内容太长，则可能会超出边缘并产生错误：再说一次，我不知道替代方法是什么。