Linearer Index obere Dreiecksmatrix

Question

Wenn ich den oberen dreieckigen Teil einer Matrix, versetzt über der Diagonalen, als lineares Array gespeichert habe, wie können die (i,j) Indizes eines Matrixelements aus dem linearen Index des Arrays extrahiert werden?

Zum Beispiel ist die lineare Anordnung [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 ist Speicher für die Matrix

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 Und wir wollen die (i, j) in einem Array wissen, zu einem in der linearen Matrix Offset entspricht, ohne Rekursion.

Ein geeignetes Ergebnis k2ij(int k, int n) -> (int, int) würde genügen, beispielsweise

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

Die Gleichungen, die aus linearem Index (i,j) Index gehen sind

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 

die inverse Operation von (i,j) Index linear Index

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

mit Verify in Python ist:

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

Lassen Sie uns zunächst einen [k] in umgekehrter Reihenfolge neu zu nummerieren. Wir erhalten:

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 

Dann k2ij (k, n) wird sich k2ij (n - k, n).

Jetzt ist die Frage, wie man k2ij (k, n) in dieser neuen Matrix berechnet. Die Folge 0, 2, 5, 9 (Indizes von Diagonalelementen) entspricht triangular numbers (nach Abzug von 1): a [n - i, n + 1 - i] = Ti - 1. Ti = i * (i + 1)/2, wenn wir also Ti kennen, ist es leicht, diese Gleichung zu lösen und i zu erhalten (siehe Formel im Artikel zum verknüpften Wiki, Abschnitt "Dreieckige Wurzeln und Tests für Dreieckszahlen"). Wenn k + 1 nicht genau eine Dreieckszahl ist, wird die Formel immer noch das nützliche Ergebnis liefern: nach dem Abrunden erhalten Sie den höchsten Wert von i, für den Ti < = k, dieser Wert von i entspricht dem Zeilenindex (von unten gezählt), in dem sich ein [k] befindet. Um die Spalte (von rechts gezählt) zu erhalten, sollten Sie einfach den Wert von Ti berechnen und subtrahieren: j = k + 1 - Ti. Um klar zu sein, diese sind nicht genau I und J von Ihrem Problem, Sie müssen sie "umdrehen".

Ich habe nicht die genaue Formel geschrieben, aber ich hoffe, dass Sie die Idee haben, und es wird jetzt trivial sein, es zu finden, nachdem Sie einige langweilige, aber einfache Berechnungen durchgeführt haben.

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

Das Folgende ist eine Implementierung in Matlab, die leicht in eine andere Sprache wie C++ übertragen werden kann. Hier nehmen wir an, die Matrix hat die Größe m * m, ind ist der Index im linearen Array. Das einzige, was anders ist, ist, dass wir hier den unteren dreieckigen Teil der Matrix Spalte für Spalte zählen, was analog zu Ihrem Fall ist (zeilenweise den oberen dreieckigen Teil zählen).

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