如何在Python中生成自然数螺旋？

Question

我希望能够创建一个函数，输入一个数字，函数将返回从1到该数字的螺旋形状（以二维数组形式）。例如，如果我将数字25传递给函数，它将返回以下结果：

我尝试了不同的方法，但都没有成功。我无法理解。
希望我已经清楚地表达了自己的意思。

- Skizo

---

听起来像是作业 -- 即使尝试失败，请发布您尝试过的内容。 - martineau

这真的不是作业..只是为了好玩.. - Skizo

数字可以是任何的吗？比如，如果你输入了23？ - Milan Zavišić

听起来像是编程面试中提出的问题的变体。我记得“打印任意矩形矩阵的所有对角遍历”与此类似。 - Jim Dennis

相关：如何在Python中创建螺旋数组？ - jfs

我正在编写一个算法，试图保留空间局部性，虽然Z曲线很有吸引力，但我认为在我的情况下螺旋更好。绝对不是作业。 ;) - SapphireSun

Answer 1

这里主要的问题是对坐标进行枚举 - 将数字与坐标匹配，然后以任何您想要的方式打印出来。

首先注意两个基本模式：

• (方向) 向右移动，然后向下移动，然后向左移动，然后向上移动，然后...（这应该很明显）
• (幅度) 移动一，然后移动一，然后移动两个，然后移动两个，然后移动三个...

因此，按照这些规则编写一个生成器，产生 数字，坐标 元组。

如果您首先设置一些辅助函数，那么它会更清晰; 我会尽可能详细：

def move_right(x,y):
    return x+1, y

def move_down(x,y):
    return x,y-1

def move_left(x,y):
    return x-1,y

def move_up(x,y):
    return x,y+1

moves = [move_right, move_down, move_left, move_up]

很容易，现在是生成器：

def gen_points(end):
    from itertools import cycle
    _moves = cycle(moves)
    n = 1
    pos = 0,0
    times_to_move = 1

    yield n,pos

    while True:
        for _ in range(2):
            move = next(_moves)
            for _ in range(times_to_move):
                if n >= end:
                    return
                pos = move(*pos)
                n+=1
                yield n,pos

        times_to_move+=1

演示：

list(gen_points(25))
Out[59]: 
[(1, (0, 0)),
 (2, (1, 0)),
 (3, (1, -1)),
 (4, (0, -1)),
 (5, (-1, -1)),
 (6, (-1, 0)),
 (7, (-1, 1)),
 (8, (0, 1)),
 (9, (1, 1)),
 (10, (2, 1)),
 (11, (2, 0)),
 (12, (2, -1)),
 (13, (2, -2)),
 (14, (1, -2)),
 (15, (0, -2)),
 (16, (-1, -2)),
 (17, (-2, -2)),
 (18, (-2, -1)),
 (19, (-2, 0)),
 (20, (-2, 1)),
 (21, (-2, 2)),
 (22, (-1, 2)),
 (23, (0, 2)),
 (24, (1, 2)),
 (25, (2, 2))]

- roippi

Answer 2

这里有一张图可以帮助你理解问题：

你可以把它想象成重复向一个 N×N 的正方形添加内容，以制作一个 （N+1）×（N+1） 的正方形：

if N is odd:
    move right one step
    move down N steps
    move left N steps
else:
    move left one step
    move up N steps
    move right N steps

每一步您都要将一个数字写到当前位置。

正如@Milan所指出的那样，您可能并不总是想要完成当前的shell（例如，如果您只想数到23）。最简单的方法是创建一个生成器函数来产生无限的步骤，然后只消耗您需要的步骤：

from itertools import count

def steps_from_center():
    for n in count(start=1):
        if n % 2:
            yield RIGHT
            for i in range(n):
                yield DOWN
            for i in range(n):
                yield LEFT
        else:
            yield LEFT
            for i in range(n):
                yield UP
            for i in range(n):
                yield RIGHT

在使用之前，我们需要决定如何存储这些值，并基于此来表示UP，DOWN，LEFT和RIGHT。

最简单的存储方式是一个二维数组，或者在Python术语中是一个列表的列表。外部列表将包含输出的行，内部列表将每个包含一行中的单元格，每个单元格可以通过my_array[y][x]进行访问，其中x从左到右递增，y从上到下递增（这与我们期望打印输出的顺序相匹配）。

这使我们能够定义我们的方向：

from collections import namedtuple

Step  = namedtuple("Step", ["dx", "dy"])
RIGHT = Step( 1,  0)
DOWN  = Step( 0,  1)
LEFT  = Step(-1,  0)
UP    = Step( 0, -1)

在分配存储空间之前，我们需要知道所需数组的大小：

from math import ceil, floor, log10, sqrt

max_i = int(input("What number do you want to display up to? "))

# how big does the square have to be?
max_n = int(ceil(sqrt(max_i)))

# here is our initialized data structure
square = [[EMPTY] * max_n for _ in range(max_n)]

# and we start by placing a 1 in the center:
x = y = max_n // 2
square[y][x] = output(1)

我在这里添加了两个额外的部分：为了使输出整洁，每个项都应该打印相同的宽度。 output() 是一个函数，它接受一个值并返回正确宽度的字符串，而 EMPTY 是该宽度的一串空格：

# how many digits in the largest number?
max_i_width = int(floor(log10(max_i))) + 1

# custom output formatter - make every item the same width
def output(item, format_string="{{:>{}}}".format(max_i_width)):
    return format_string.format(item)

EMPTY = output("")

现在所有的元素都已经准备好了，我们可以生成螺旋形图案：

for i, step in enumerate(steps_from_center(), start=2):
    if i > max_i:
        break
    else:
        x += step.dx
        y += step.dy
        square[y][x] = output(i)

并将其打印出来：

print("\n".join(" ".join(row) for row in square))

而且它的运行速度如下：

What number do you want to display up to? 79
73 74 75 76 77 78 79      
72 43 44 45 46 47 48 49 50
71 42 21 22 23 24 25 26 51
70 41 20  7  8  9 10 27 52
69 40 19  6  1  2 11 28 53
68 39 18  5  4  3 12 29 54
67 38 17 16 15 14 13 30 55
66 37 36 35 34 33 32 31 56
65 64 63 62 61 60 59 58 57

- Hugh Bothwell

Answer 3

有几个步骤需要解决这个问题。首先，设置一个网格。网格的大小需要等于下一个更高的完全平方数；例如，如果输入23，则需要一个 5 × 5 (25) 网格，或者如果输入31，则需要一个 6 × 6 网格（36）。接下来，在“当前位置”（即中心位置）存储数字序列的下一个值。在每一步中，检查基本方向并将“当前位置”移动到最靠近中心且未填充的位置，有偏东方（处理初始步骤，在 N、S、E、W 中没有差异的情况下）。直到迭代器完成为止。

---

编辑：我真的很喜欢这个问题，所以我写了一个好的解决方案。我已经有一段时间没有写 Python 了，所以这可能不是最优雅的解决方案，但仍然可以胜任。

from functools import partial
from math import ceil, sqrt

def gen_grid(n):
  grid_size = int(ceil(sqrt(n)))
  return [[None for _ in range(grid_size)] for _ in range(grid_size)]

def valid_coord(grid, coord):
  try:
    return grid[coord[0]][coord[1]] is None
  except:
    return False

def origin(size):
  adjustment = 1 if size % 2 == 0 else 0
  return (size / 2 - adjustment), (size / 2 - adjustment)

north = lambda y, x: (y - 1, x)
south = lambda y, x: (y + 1, x)
east = lambda y, x: (y, x + 1)
west = lambda y, x: (y, x - 1)

directions = lambda y, x: [east(y, x), south(y, x), west(y, x), north(y, x)]
distance = lambda c, nxt: sqrt((c[0] - nxt[0]) ** 2 + (c[1] - nxt[1]) ** 2)

def walk_grid(nums):
  grid = gen_grid(len(nums))
  center = origin(len(grid[0]))
  current_position = center
  center_distance = partial(distance, center)

  for n in nums:
    y, x = current_position
    grid[y][x] = n
    unseen_points = [c for c in directions(y, x) if valid_coord(grid, c)]
    if n != nums[-1]:
      current_position = sorted(unseen_points, key=center_distance)[0]

  return grid

def print_grid(highest):
  result = walk_grid(range(1, highest + 1))
  for row in result:
    for col in row:
      print "{:>4}".format(col if col is not None else ''),  
    print "\n"

示例输出：

In [2]: grid.print_grid(25)
  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 

- asthasr

---

很遗憾这个问题被关闭了，但我用numpy和自定义的Vec2类写了一个解决方案，其中你有一个点和一个方向向量，然后将它们相加。当你到达数组的末尾时，转90度：direction = Vec2(-direction.y, direction.x)，其中方向初始化为Vec2(1, 0)。这些都很有趣！（我的螺旋代码从左上角开始，一直工作到中心，只需反转生成的列表即可从内向外走！） - SapphireSun

Answer 4

所以我假设你已经可以在某种程度上确定数组的大小和“1”的位置。现在你需要一个允许你改变方向和计数器的函数。

def get_new_direction(direction):
  switch direction:
     case E: return S
     case S: return W
     case W: return N
     case N: return E

i,j = initial_coordinates_of_the_one
direction = right
steps = 1
next_number = 1

while not done:
  place(next_number, i, j)
  i,j = get_coordinates_after_move(direction, steps)
  direction = get_new_direction(direction)
  next_number++
  if iteration is even:
    steps++

这只是一个草图。还有一些缺失的部分（但很容易想到）：

• 如何实现这些函数
• 如何在遵循一个方向时设置多个数字

- Pavel

---

此外，Python 没有 switch 语句或运算符 ++。 - Davidmh

@Davidmh 这显然是伪代码。 - poke