線性指數上三角矩陣

如果我有一個矩陣的上三角部分，在對角線上方的偏移量，存儲爲線性陣列，矩陣元素的指數如何從數組的線性索引中提取？線性指數上三角矩陣

例如，線性陣列[a0, a1, a2, a3, a4, a5, a6, a7, a8, a9爲矩陣

0 a0 a1 a2 a3 0 0 a4 a5 a6 0 0 0 a7 a8 0 0 0 0 a9 0 0 0 0 0 存儲和我們想知道第（i，j）的陣列中的對應於在所述線性矩陣偏移索引，且無需遞歸。

合適的結果，將k2ij(int k, int n) -> (int, int)滿足例如

k2ij(k=0, n=5) = (0, 1) k2ij(k=1, n=5) = (0, 2) k2ij(k=2, n=5) = (0, 3) k2ij(k=3, n=5) = (0, 4) k2ij(k=4, n=5) = (1, 2) k2ij(k=5, n=5) = (1, 3) [etc]

來源

2014-11-23 Robert T. McGibbon

爲最後一列的元素寫一個公式。爲了使它更容易編寫一個從行號計算線性索引的公式（列號是固定的），然後將其反轉。從那裏繼續一個通用公式。 – 2014-11-23 06:57:44

請注意，此處介紹的解決方法也可以用於列出N次事件的組合（無需重複），而不需要任何迭代/遞歸。 – 2015-03-30 15:03:40

從線性索引去(i,j)指數方程是

i = n - 2 - floor(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5) 
j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2

的逆運算，從(i,j)索引到線性指數是

k = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1

驗證在Python與：

from numpy import triu_indices, sqrt 
n = 10 
for k in range(n*(n-1)/2): 
    i = n - 2 - int(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5) 
    j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2 
    assert np.triu_indices(n, k=1)[0][k] == i 
    assert np.triu_indices(n, k=1)[1][k] == j 

for i in range(n): 
    for j in range(i+1, n): 
     k = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1 
     assert triu_indices(n, k=1)[0][k] == i 
     assert triu_indices(n, k=1)[1][k] == j

來源

2014-11-23 11:44:37

完美！這幫助我減少了線性程序中的變量數量！ – linello 2015-02-12 11:25:12

'i = ...' – Squidly 2015-03-23 11:30:43

（@MrBones：固定感謝） – 2015-03-24 02:53:54

首先，讓我們在重新編號相反的順序一個[K]。我們將得到：

0 a9 a8 a7 a6 
0 0 a5 a4 a3 
0 0 0 a2 a1 
0 0 0 0 a0 
0 0 0 0 0

然後k2ij（k，n）將變成k2ij（n-k，n）。

現在的問題是，如何計算這個新矩陣中的k2ij（k，n）。序列0,2,5,9（對角線元素的索引）對應於triangular numbers（減去1之後）：a [n-i，n + 1-i] = Ti-1 Ti = i *（i + 1）/2，所以如果我們知道Ti，很容易解出這個方程並得到i（參見鏈接的wiki文章「三角形根的三角形根和測試」一節中的公式）。如果k + 1不完全是一個三角形數字，該公式仍然會給你有用的結果：在將其舍入後，將得到i的最高值，對此，我的這個值對應於行索引（從底部開始計算），其中a [k]位於其中。爲了得到列（從右邊算起），你應該簡單地計算Ti的值並減去它的值：j = k + 1 - Ti。要清楚的是，這些並不是你的問題中的我和j，你需要「翻轉」它們。

我沒有寫出確切的公式，但我希望你有這個想法，現在在執行一些無聊但簡單的計算後找到它就變得微不足道了。

來源

2014-11-23 07:57:55

在python中：

def k2ij(k, n): 
    rows = 0 
    for t, cols in enumerate(xrange(n - 1, -1, -1)): 
     rows += cols 
     if k in xrange(rows): 
      return (t, n - (rows - k)) 
    return None

來源

2014-11-23 17:46:15 smac89

以下是matlab中的一個實現，它可以很容易地轉移到另一種語言，比如C++。在這裏，我們假設矩陣的大小爲m * m，ind是線性數組中的索引。唯一不同的是，在這裏，我們計算矩陣列的下三角部分，這與您的案例類似（逐行計算上三角部分）。

function z= ind2lTra (ind, m) 
    rvLinear = (m*(m-1))/2-ind; 
    k = floor((sqrt(1+8*rvLinear)-1)/2); 

    j= rvLinear - k*(k+1)/2; 

    z=[m-j, m-(k+1)];

來源

2015-04-13 21:17:08 study

線性指數上三角矩陣

回答

相關問題