python - 对角线(之字形)遍历坐标的索引

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 的正方形，它包含索引 0 到 9。

如果您查看每列顶部的数字，您会发现这些是“三角数”，它们是从 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，在此之前发生了。如果您需要更可靠的例程来计算整数平方根，请告诉我。