对角线（之字形）遍历中坐标的索引

Question

所以我有一个 4x4 矩阵，如下所示

 |0 1 2 3
-+-------
0|0 1 3 6
1|2 4 7 a
2|5 8 b d
3|9 c e f

我按照其中的十六进制字符指定的顺序遍历它。所以从 (0, 0) 开始，然后是 (1, 0)、(0, 1)、(2, 0)、(1, 1)、(0, 2)...

所以这是代码：

def diagonal(n):
    for a in range(n):
        for b in range(a + 1):
            yield a - b, b
    for a in range(n - 1):
        for b in range(n - a - 1):
            yield n - b - 1, b + 1 + a

迭代此给出

for x, y in diagonal(4):
    print((x, y))

# (0, 0)
# (1, 0)
# (0, 1)
# (2, 0)
# (1, 1)
# (0, 2)
# (3, 0)
# (2, 1)
# (1, 2)
# (0, 3)
# (3, 1)
# (2, 2)
# (1, 3)
# (3, 2)
# (2, 3)
# (3, 3)

这正是我的意图。我所坚持的部分是尝试创建一个函数，我给它索引，它给我坐标。所以对于我的 4x4 矩阵，（这仍然是十六进制）

0 -> (0, 0)
1 -> (1, 0)
2 -> (0, 1)
3 -> (2, 0)
4 -> (1, 1)
5 -> (0, 2)
6 -> (3, 0)
7 -> (2, 1)
8 -> (1, 2)
9 -> (0, 3)
a -> (3, 1)
b -> (2, 2)
c -> (1, 3)
d -> (3, 2)
e -> (2, 3)
f -> (3, 3)

我打算继续使用可变大小的方阵，因此我不能将这些值硬编码到字典中。

我已经修补了几个小时试图让它发挥作用，但我一生都无法让它发挥作用。

这不是家庭作业，只是我在业余时间做的事情，它慢慢地让我陷入困境。

如果有任何不清楚的地方，请随时询问。

提前致谢。

编辑：我想有人会对这篇文章Traverse Matrix in Diagonal strips发表评论，该文章类似，但与我的第一个函数一样，它仅迭代坐标，并且我无法从索引计算出坐标。

Answer 1

这是一个似乎可以完成您想要的功能的函数。代码后面有解释。

from math import sqrt

def triangular(n):
    return n * (n + 1) // 2

def coords_from_index(ndx, n=4):
    if ndx < triangular(n):
        basecol = (int(sqrt(8 * ndx + 1)) - 1) // 2
        row = ndx - triangular(basecol)
        col = basecol - row
    else:
        oldcol, oldrow = coords_from_index(n**2 - 1 - ndx, n)
        row = n - 1 - oldrow
        col = n - 1 - oldcol
    return col, row

# Test code
n = 4
for ndx in range(n**2):
    print(hex(ndx)[2:], '->', coords_from_index(ndx, n))

该测试代码的打印输出是：

0 -> (0, 0)
1 -> (1, 0)
2 -> (0, 1)
3 -> (2, 0)
4 -> (1, 1)
5 -> (0, 2)
6 -> (3, 0)
7 -> (2, 1)
8 -> (1, 2)
9 -> (0, 3)
a -> (3, 1)
b -> (2, 2)
c -> (1, 3)
d -> (3, 2)
e -> (2, 3)
f -> (3, 3)

这是我的代码的简要说明。

就像您按顺序生成坐标的代码一样，我对正方形的左上三角形与右下三角形的处理方式有所不同。让我们首先看一下左上角的三角形，它的大小平方包括到 的4索引。09

如果您查看每列中顶部的数字，您会发现这些是“三角形数字”，它们是从 开始的连续整数的总和0。所以顶行是0, 0+1, 0+1+2, 和0+1+2+3。这些数字的众所周知的公式是

triangular(n) = n * (n + 1) // 2

所以我为此编写了一个小例程。如果你知道三角数（称之为ndx）并且想要找到n，你可以使用代数来求解二次方程，你会得到

n = (sqrt(8 * ndx + 1) - 1) // 2

如果将 替换为 ，sqrt您int(sqrt(将获得与三角形数相同的结果，并且还可以获得ndx位于两个三角形数之间的任何数字的“基”数。然后，您可以使用索引和“基数”来查找索引对应的列和行。

现在，如果您查看右下三角形（其中包括a到 的索引f），您会发现它与左上三角形对称。我选择使用这种对称性来计算任何这些索引的行和列。我本可以更直接地计算它们，但我使用的方法效果很好。

请注意，如果您使用非常大的 和 值n，ndx则int(sqrt(由于浮点运算的变幻莫测，并不总是给出正确的答案。但在此之前ndx需要非常大，大约为。2**50如果您需要更可靠的例程来计算整数平方根，请告诉我。