arrays - 访问压缩对称距离矩阵的元素

Question

假设您有一个对称距离矩阵A。例如A是4*4（矩阵上方和左侧的数字是测量距离的元素的索引，我们只使用下三角形）：

   0   1   2   3  
   _____________
0 |0   0   0   0
1 |a10 0   0   0
2 |a20 a21 0   0
3 |a30 a31 a32 0

所以，基本上，如果A是n*n，我们只有n*(n-1)/2有用的条目。消除对角线上的零，我们得到以下矩阵（类似于 Matlab 和 R 的矩阵）：

A=     0   1   2  
       _________
    1 |a10 0   0
    2 |a20 a21 0
    3 |a30 a31 a32

np = n*(n-1)/2接下来，我们可以有效地将这个矩阵存储在包含元素的打包格式的一维数组中：

Ap = {a10, a20, a21, a30, a31, a32}

这可以加快许多搜索（例如搜索最接近的元素对等）并节省大量空间（在n很大时很有用）

访问元素之间的距离i和j等效于访问j+i(i-1)/2压缩矩阵中的元素，即A[i,j] = Ap[j+i(i-1)/2]for i>0, j<n-1, j<i。

问题是如果我们处于相反的情况，即我们在压缩矩阵中有元素的索引，Ap我们如何恢复原始的两个索引：Given Ap[x]，what arei和jin A，这样Ap[x] = A[i,j]。

谢谢！

score 0 · Accepted Answer

0

好的，我找到了答案：

i = floor{ (1 + sqrt[1 + 8*x])/2 }
j = x - i

于 2013-08-25T23:51:18.283 回答

1 回答 1