Ottenere la riga e colonna di una matrice triangolare, in base all'indice

Question

sto lavorando con una matrice triangolare MxM, che ha la seguente forma:

M = [m00 m10 m20 m30 m40] 
    [m11 m21 m31 m41 ] 
    [m22 m32 m42  ] 
    [m33 m43   ] 
    [m44    ] 

Se è più facile immaginare questo in termini di indici, sarebbe simile a questa:

M = [0 1 3 6 10] 
    [2 4 7 11 ] 
    [5 8 12 ] 
    [9 13  ] 
    [14  ] 

so che questo modo di indicizzazione potrebbe apparire strano ma sarebbe molto più facile se potessi mantenere il sistema di indicizzazione in quanto è in ordine per questo modulo per lavorare bene con gli altri.

Sono in difficoltà con un algoritmo che prende un indice e una dimensione della matrice che può restituire la riga e la colonna in cui cade l'indice indicato. Idealmente avrei 2 funzioni come queste:

int getRow (int index, int size); 
int getCol (int index, int size); 

Così getRow (7, 5) sarebbero tornati 3

E getCol (7, 5) sarebbe tornato 1

Mi sono imbattuto in questa discussione già, ma io non riesco a modificare la soluzione dato lì per lavorare per il modo in cui sto indicizzando.

algorithm for index numbers of triangular matrix coefficients

Answer 1

Nuova risposta

È possibile trovare il row e column utilizzando le seguenti formule:

int row = floor(-0.5 + sqrt(0.25 + 2 * index)); 
int triangularNumber = row * (row + 1)/2; 
int column = index - triangularNumber; 

Questo funziona perché la prima voce in ogni riga è un triangular number (0 , 1, 3, 6, 10, 15, ...). Quindi il più grande numero triangolare che è inferiore a index ci dà il row. Quindi column è semplicemente la differenza tra index e quel numero triangolare.

Inoltre, si noti che non è necessario il parametro M.

---

Vecchio risposta

Questo codice vi darà sia la row e column di index.

int triangularNumber = 0; 
int row = 0; 
while (triangularNumber + row < index) { 
    row ++; 
    triangularNumber += row; 
} 
int column = index - triangularNumber;