Macierz górna trójkątna o indeksie liniowym

Question

Jeśli mam górną trójkątną część macierzy, przesunięcie powyżej przekątnej, przechowywane jako tablica liniowa, w jaki sposób można wyliczyć indeksy elementu matrycowego z liniowego indeksu macierzy?

Na przykład tablica liniowa [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 jest do przechowywania matrycy

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 chcemy poznać (i, j) indeks w tablicy odpowiada przesunięcie w matrycy liniowej, bez rekursji.

Odpowiedni wynik, k2ij(int k, int n) -> (int, int) spełniałoby np

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

Równania te są prowadzone z indeksem liniowego, (i,j) wskaźnika są

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 

operacji odwrotnej, z (i,j) wskaźnika do wskaźnika liniowego

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

Sprawdź w Pythona:

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

Najpierw przenumerować [k] w odwrotnej kolejności. Dostaniemy:

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 

Wtedy k2ij (k, n) stają k2ij (n - k, n).

Teraz pytanie brzmi: jak obliczyć k2ij (k, n) w tej nowej macierzy. Sekwencja 0, 2, 5, 9 (indeksy elementów diagonalnych) odpowiada triangular numbers (po odjęciu 1): a [n - i, n + 1 - i] = Ti - 1. Ti = i * (i + 1)/2, więc jeśli znamy Ti, łatwo jest rozwiązać to równanie i uzyskać i (zobacz wzór w łączonym artykule wiki, sekcja "Triangular roots and tests for triangular numbers"). Jeśli k + 1 nie jest dokładnie liczbą trójkątną, formuła da ci jeszcze użyteczny wynik: po zaokrągleniu w dół otrzymasz najwyższą wartość i, dla której Ti < = k, ta wartość i odpowiada indeks wiersza (licząc od dołu), w którym znajduje się [k]. Aby uzyskać kolumnę (licząc od prawej), należy po prostu obliczyć wartość Ti i odjąć ją: j = k + 1 - Ti. Aby być jasnym, nie są to jednak i i j z twojego problemu, musisz je "odwrócić".

Nie napisałem dokładnej formuły, ale mam nadzieję, że wpadłeś na ten pomysł, a teraz będzie to banalne, po odnalezieniu nudnych, ale prostych obliczeń.

Answer 3

W 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

Poniżej znajduje się implikacja w programie Matlab, którą można łatwo przenieść na inny język, np. C++. Zakładamy, że macierz ma rozmiar m * m, ind jest indeksem w macierzy liniowej. Jedyną różnicą jest to, że tutaj liczymy dolną trójkątną część kolumny macierzy po kolumnie, która jest analogiczna do twojego przypadku (licząc górną trójkątną część wiersza po wierszu).

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