46

行列の上三角部分を対角線の上にオフセットし、線形配列として格納している場合(i,j)、配列の線形インデックスから行列要素のインデックスを抽出するにはどうすればよいですか?

たとえば、線形配列[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]
4

5 に答える 5

54

線形インデックスから(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-23T11:44:37.700 に答える
4

以下は、C++ などの別の言語に簡単に転送できる matlab での実装です。ここで、行列のサイズが 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-13T21:17:08.280 に答える
1

Python 2 の場合:

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-23T17:46:15.307 に答える