线性指数上三角矩阵

如果我有一个矩阵的上三角部分，在对角线上方的偏移量，存储为线性阵列，矩阵元素的指数如何从数组的线性索引中提取？线性指数上三角矩阵

例如，线性阵列[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

线性指数上三角矩阵

回答

相关问题