用于查找对的压缩矩阵函数

对于一组观察结果：

[a1,a2,a3,a4,a5]

他们的成对距离

d=[[0,a12,a13,a14,a15]
   [a21,0,a23,a24,a25]
   [a31,a32,0,a34,a35]
   [a41,a42,a43,0,a45]
   [a51,a52,a53,a54,0]]

以压缩矩阵形式给出（上面的上三角，计算公式为scipy.spatial.distance.pdist ):

c=[a12,a13,a14,a15,a23,a24,a25,a34,a35,a45]

问题是，鉴于我在压缩矩阵中有索引，是否有一个函数（最好在 python 中）f快速给出哪两个观察值用于计算它们？

f(c,0)=(1,2)
f(c,5)=(2,4)
f(c,9)=(4,5)
...

我尝试过一些解决方案，但没有一个值得一提:(

压缩矩阵的索引公式为

index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2 + j - i - 1

Where i是行索引，j是列索引，并且d是原始 (d X d) 上三角矩阵的行长度。

考虑当索引引用原始矩阵中某些行的最左边的非零条目时的情况。对于所有最左边的索引，

j == i + 1

so

index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2 + i + 1 - i - 1
index = d * (d - 1) / 2 - (d - i) * (d - i - 1) / 2

通过一些代数，我们可以将其重写为

i ** 2 + (1 - (2 * d)) * i + 2 * index == 0

然后我们可以使用二次公式来求方程的根，我们只需 关心积极的根源。

如果这个索引确实对应于最左边的非零单元格，那么我们得到一个正整数作为解 对应于行号。然后，找到列号只是算术。

j = index - d * (d - 1) / 2 + (d - i) * (d - i - 1)/ 2 + i + 1

如果索引不对应于最左边的非零单元格，那么我们将找不到整数根，但我们可以将正根的下限作为行号。

def row_col_from_condensed_index(d,index):
    b = 1 - (2 * d) 
    i = (-b - math.sqrt(b ** 2 - 8 * index)) // 2
    j = index + i * (b + i + 2) // 2 + 1
    return (i,j)  

如果你不知道d，你可以从压缩矩阵的长度算出。

((d - 1) * d) / 2 == len(condensed_matrix)
d = (1 + math.sqrt(1 + 8 * len(condensed_matrix))) // 2