如何在python中制作螺旋？

Question

我想创建一个函数,我给它一个数字,函数返回一个从1到该数字的螺旋(在二维数组中).例如,如果我将数字25赋予函数,它将返回如下内容:

我尝试了不同的方法,但没有成功.我只是想不通.
希望我能正确解释自己.

Answer 1

这里的问题主要是枚举坐标 - 将数字与坐标匹配,然后根据需要打印出来.

首先注意两个基本模式:

• (方向)向右移动,然后向下移动,然后向左移动,然后向上移动,然后......(这有望显而易见)
• (幅度)移动一个,然后一个,然后是两个,然后是两个,然后是三个......

因此,使用这些规则,编写一个产生number, coordinates元组的生成器.

如果你先设置一些辅助函数,它是最清楚的; 我会特别冗长:

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

Answer 2

这是一个帮助您思考问题的图表:

您可以将此视为重复添加到NxN方格以生成(N + 1)x(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.

最简单的存储是2d数组,或者用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

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