对角蛇填充阵列

Question

Python 3.7.我试图以对角线蛇形图填充多维数组(n*m大小):

1   3   4   10  11  21
2   5   9   12  20  22
6   8   13  19  23  30
7   14  18  24  29  31
15  17  25  28  32  35
16  26  27  33  34  36

我有一个n x n大小的功能,它的工作正常.但是对于n x m尺寸它会返回:

1 3  4  10 14

2 5  9  15 20

6 8  16 19 19

7 17 18 20 21

我的代码:

def method1(i, j, n, m):
    num = i+j
    summ = num * (num + 1) >> 1
    s = n * m
    if num > n-1:
        t = 2*(n-1) - (i+j) + 1
        s -= t*(t+1) >> 1

    if num & 1:
        if num > n-1:
            return s + (n-i)
        else:
            return summ + j+1
    if num > n-1:
        return s + (n-j)
    else:
        return summ + i+1

for i in range(n):
    for j in range(m):
        print(method1(i, j, n, m), end=" ")
    print('\n')

我究竟做错了什么？PS你的答案可以是任何语言.

Answer 1

这是一个矢量化解决方案:

def tr(z):
    return z*(z+1)//2

def snake(Y, X):
    y, x = np.ogrid[:Y, :X]
    mn, mx = np.minimum(X, Y), np.maximum(X, Y)
    return (1 + tr(np.clip(x+y, None, mn))
            + mn * np.clip(x+y - mn, 0, None)
            - tr(np.clip(x+y - mx, 0, None))
            + ((x+y) & 1) * (x - np.clip(x+y + 1 - Y, 0, None))
            + ((x+y + 1) & 1) * (y - np.clip(x+y + 1 - X, 0, None)))

演示:

>>> snake(7, 3)
array([[ 1,  3,  4],
       [ 2,  5,  9],
       [ 6,  8, 10],
       [ 7, 11, 15],
       [12, 14, 16],
       [13, 17, 20],
       [18, 19, 21]])
>>> snake(2, 4)
array([[1, 3, 4, 7],
       [2, 5, 6, 8]])

解释器:

该函数tr计算三角形中元素的数量,该元素大约是半个正方形(因为我们包括对角线,所以更多一点).这用于snake计算每个对角线的偏移量; 对角线索引x+y.

更确切地说,return语句中的前三行计算对角线偏移量.第一行计算左上角三角形中的对角线,第二行计算全长对角线以及右下角三角形中的对角线; 它也计算全长 - 第三行纠正了这一点.

最后两行在对角线内计算.两个中的第一个在右上方向,第二个在左下方向.请注意,右上角偏移量等于x从左边缘开始的所有对角线的坐标.校正项(np.clip ...)用于从底边开始的对角线.类似地,左下偏移是y如果我们从顶部边缘开始并且如果我们从右边缘开始则需要校正.

Answer 2

不清楚你做错了什么，但以下代码应该可以工作：

import numpy as np

n = 4
m = 5

x, y = (0, 0)
ux, uy = (1, -1)

a = np.zeros((n, m))
for i in range(n*m):
  print((x, y), i+1)
  a[x, y] = i + 1
  x, y = (x + ux, y + uy)
  if y == m:
    print('right side')  # including corner
    y = m - 1
    x += 2
  elif x == n:
    print('bottom side')  # including corner
    x = n - 1
    y += 2
  elif x == -1:
    print('top side')
    x = 0
  elif y == -1:
    print('left side')
    y = 0
  else:
    continue
  ux, uy = -ux, -uy
print(a)

输出：

(0, 0) 1
left side
(1, 0) 2
(0, 1) 3
top side
(0, 2) 4
(1, 1) 5
(2, 0) 6
left side
(3, 0) 7
(2, 1) 8
(1, 2) 9
(0, 3) 10
top side
(0, 4) 11
(1, 3) 12
(2, 2) 13
(3, 1) 14
bottom side
(3, 2) 15
(2, 3) 16
(1, 4) 17
right side
(2, 4) 18
(3, 3) 19
bottom side
(3, 4) 20
right side
[[ 1.  3.  4. 10. 11.]
 [ 2.  5.  9. 12. 17.]
 [ 6.  8. 13. 16. 18.]
 [ 7. 14. 15. 19. 20.]]

为了写这个，画个图很有帮助。