对角蛇填充数组

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 大小它 returns:

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

我做错了什么？ P.S。您的回答可以是任何语言。

Answer 1

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

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

写到这里，画个图帮了大忙

Answer 2

这是一个向量化的解决方案：

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 3

编辑：

这是一个基本相同的算法版本，但没有任何循环：

def snake_matrix(n):
    # Make sequences: [0, 0, 1, 0, 1, 2, 0, 1, 2, 3, ...]
    i = np.arange(n)
    c = np.cumsum(i)
    reps = np.repeat(c, i + 1)
    seqs = np.arange(len(reps)) - reps
    # Make inverted sequences: [0, 1, 0, 2, 1, 0, 3, 2, 1, 0, ...]
    i_rep = np.repeat(i, i + 1)
    seqs_inv = i_rep - seqs
    # Select sequences for row and column indices
    seq_even_mask = (i_rep % 2 == 0)
    # Row inverts even sequences
    row = np.where(seq_even_mask, seqs, seqs_inv)
    # Column inverts odd sequences
    col = np.where(~seq_even_mask, seqs, seqs_inv)
    # Mirror  for lower right corner
    row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
    col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
    m = np.empty((n, n), dtype=int)
    m[row, col] = np.arange(n * n)
    return m

有趣的是，经过几个基准测试后，似乎根据大小，这可能比以前的算法快，也可能不快。

这是另一个使用 NumPy 的解决方案。我不知道是否有任何其他方法可以使它变得更好（没有循环，或者在这种情况下是列表理解），但至少它不会遍历每个元素。不过这只适用于方阵。

import numpy as np

def snake_matrix(n):
    # Sequences for indexing top left triangle: [0], [0, 1], [0, 1, 2], [0, 1, 2, 3]...
    seqs = [np.arange(i + 1) for i in range(n)]
    # Row indices reverse odd sequences
    row = np.concatenate([seq if i % 2 == 0 else seq[::-1] for i, seq in enumerate(seqs)])
    # Column indices reverse even sequences
    col = np.concatenate([seq if i % 2 == 1 else seq[::-1] for i, seq in enumerate(seqs)])
    # Indices for bottom right triangle "mirror" top left triangle
    row = np.concatenate([row, n - 1 - row[len(row) - n - 1::-1]])
    col = np.concatenate([col, n - 1 - col[len(col) - n - 1::-1]])
    # Make matrix
    m = np.empty((n, n), dtype=int)
    m[row, col] = np.arange(n * n)
    return m

print(snake_matrix(6))

输出：

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

在 OEIS A319571 sequence 中有一些关于这种枚举的更多信息（尽管它指的是无限网格的一般顺序，在这种情况下，您将有一个枚举从左上角开始，另一个在右下角）。

对角蛇填充数组

Diagonal snake filling array

python

arrays

numpy

matrix

diagonal