Matrice triangolare superiore dell'indice lineare

Question

Se si dispone della porzione triangolare superiore di una matrice, spostata sopra la diagonale, memorizzata come matrice lineare, come si possono estrarre gli indici di un elemento di matrice dall'indice lineare dell'array?

Ad esempio, l'array lineare [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 è immagazzinaggio per la matrice

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 e vogliamo conoscere il (i, j) Indice nella matrice corrispondente ad un offset nella matrice lineare senza ricorsione.

Un risultato adatto, k2ij(int k, int n) -> (int, int) sarebbe soddisfare, ad esempio

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]

Answer 1

Le equazioni che vanno dall'indice lineare (i,j) indice sono

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 

L'operazione inversa, da (i,j) indice all'indice lineare è

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

Verificare in pitone con:

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 

Answer 2

Innanzitutto, diamo rinumerare un [k] in ordine inverso. Otterremo:

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 

Poi k2ij (k, n) diventerà k2ij (n - k, n).

Ora, la domanda è, come calcolare k2ij (k, n) in questa nuova matrice. La sequenza 0, 2, 5, 9 (indici di elementi diagonali) corrisponde a triangular numbers (dopo la sottrazione di 1): a [n - i, n + 1 - i] = Ti - 1. Ti = i * (i + 1)/2, quindi se conosciamo Ti, è facile risolvere questa equazione e ottenere i (vedere la formula nell'articolo wiki collegato, sezione "Radici triangolari e test per numeri triangolari"). Se k + 1 non è esattamente un numero triangolare, la formula ti darà comunque il risultato utile: dopo averlo arrotondato, otterrai il valore più alto di i, per cui Ti < = k, questo valore di i corrisponde al indice di riga (contando dal basso), in cui si trova [k]. Per ottenere la colonna (contando da destra), devi semplicemente calcolare il valore di Ti e sottrarlo: j = k + 1 - Ti. Per essere chiari, questi non sono esattamente i e j dal tuo problema, devi "capovolgerli".

Non ho scritto la formula esatta, ma spero che tu abbia avuto l'idea, e ora sarà banale trovarla dopo aver eseguito calcoli noiosi ma semplici.

Answer 3

In 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 

Answer 4

Il seguente è un impianto in MATLAB, che può essere facilmente trasferito in un'altra lingua, come C++. Qui, supponiamo che la matrice abbia dimensione m * m, ind è l'indice nell'array lineare. L'unica cosa diversa è che qui contiamo la parte triangolare inferiore della matrice colonna per colonna, che è analogo al tuo caso (contando la parte triangolare superiore riga per riga).

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)];