代码之家 › 专栏 › 技术社区 › dangee1705

对角线(之字形)导线中坐标的索引

matrix python

dangee1705 · 技术社区 · 7 年前

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

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)

我打算转到可变大小的方阵,所以我不能把这些值硬编码到dict中。

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

这不是家庭作业,只是我在业余时间正在做的事情,它正慢慢地把我逼上绝路。

提前谢谢。

编辑: 我想有人会对这篇文章发表评论 Traverse Matrix in Diagonal strips 这与我的第一个函数类似,但它只在坐标上迭代,我无法从索引中计算出坐标。

2 回复 | 直到 7 年前

Rory Daulton 7 年前

这里有一个函数,它似乎可以满足您的需要。代码后面有一个解释。

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 ,您可以看到左上角的三角形是对称的。我选择使用这种对称性来计算这些索引的行和列。我本可以更直接地计算它们,但我使用的方法效果很好。

请注意,如果使用的值非常大和 ndx 那由于浮点运算的反复无常性,不总是给出正确的答案。但是 ndx 需要大的,大约 2**50 ,在那之前。如果您需要更可靠的例程来计算整数平方根,请告诉我。

Gal Avineri 7 年前

这基本上是一个算法问题:)

推断坐标

作为初始步骤,在每个对角线中准备第一个线性索引的数组。
[0, 1, 3, 6, 10, 30, 15] .
这些基本上是垃圾箱。这意味着所有保持 a[i] <= index < a[i+1]

然后,在接收索引时:

您可以通过查找 D bin[d] <= index < bin[d]
找到对角线上的位置。
这是bin[d]和索引之间的距离。这意味着如果 索引-bin[d]=k ,则索引位于该对角线的第k个位置。
推断坐标。

如果x<=M-1比我们在对角线上(k,d-k)大

当我们插入前面找到的k时,我们将找到所需的坐标。

实施

def ind2cor(index):
    d = bisect_left(a, index)
    if index != a[d]:
        d -= 1

    k = index - a[d]

    if d <= m-1:
        return k, d - k
    else:
        return d - (m - 1) + k, (m - 1) - k

m = 4
a = [0, 3, 6, 10, 13, 15]
for i in range(16):
    print('{}: {}'.format(i, ind2cor(i)))

产量:

0: (0, 0)
1: (0, 1)
2: (1, 0)
3: (0, 2)
4: (1, 1)
5: (2, 0)
6: (0, 3)
7: (1, 2)
8: (2, 1)
9: (3, 0)
10: (1, 3)
11: (2, 2)
12: (3, 1)
13: (2, 3)
14: (3, 2)
15: (3, 3)

def genereate_diagonal_indices(m):
    a = [0]
    for i in range(1, m):
        a.append(a[-1] + i)
    for i in range(m, 1, -1):
        a.append(a[-1] + i)
     return a

所以你可以用 a = genereate_diagonal_indices(m) 而不是在上面的代码中。