訪問填充對稱距離矩陣的元素

假設您有一個對稱距離矩陣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 2具有）：

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大）

訪問元件0123之間的距離和j相當於訪問打包矩陣中的元素j+i(i-1)/2，即A[i,j] = Ap[j+i(i-1)/2]對於i>0, j<n-1, j<i。

的問題是，如果我們是在相反的情況，即我們有元素的填充基質Ap指標，我們該如何恢復原來的兩個指標：鑑於Ap[x]，什麼是Ai和j，例如那Ap[x] = A[i,j]。

謝謝！

好了，我找到了答案：

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

2013-08-25 23:51:18

回答