elementi Mappatura a triangolo superiore 2D e inferiore triangolo a struttura lineare

Question

Ho una matrice M che è di dimensioni NxN, dove M (i, j) = M (j, i)

desidero rappresentare questo struttura come (N² + N)/2 array lineare K, per risparmiare spazio. Il mio problema sta arrivando con la formula che mapperà un M (min (i, j), min (i, j)) in un intervallo [0, (N^2)/2)

Di seguito è riportata una mappatura di una matrice 3x3 con indici per K schiera lineare, X significa non esistono tali cellule e invece la loro trasposizione deve essere usato:

X456 
XX78 
XXX9 

Qui è una matrice 7x7 con indici per la schiera lineare K

 0 1 2 3 4 5 6 
0 00 01 02 03 04 05 06 
1  07 08 09 10 11 12 
2  13 14 15 16 17 
3   18 19 20 21 
4    22 23 24 
5     25 26 
6     27 

al momento ho il seguente

int main() 
{ 
    const unsigned int N = 10; 
    int M[N][N]; 

    int* M_ = &(M[0][0]); 

    assert(M[i][j] = M_[N * min(i,j) + max(i,j)]); 

    //int* K = ..... 
    //assert(M[i][j] = K[.....]); 

    return 0; 
} 

Answer 1

Assumendo y> = x, è possibile utilizzare una "mappatura" come

index := x + (y+1)*y/2 

che produrrebbe

0 

1 2 

3 4 5 

6 7 8 9 

10 11 12 13 14 

Se x> y, proprio di swap xe y. Hai bisogno di (dimensione + 1) * dimensione/2 elementi di spazio per questo.

Answer 2

Per andare verso opposto che è quello che serviva:

void printxy(int index) 
{ 
    int y = (int)((-1+sqrt(8*index+1))/2); 
    int x = index - y*(y+1)/2; 
} 

Answer 3

Ecco la mappatura corretta:

 for (int i = 0; i < n; i++) { 
      for (int j = i; j < n; j++) { 
        int idx = sum(n) - sum(n - i) + j - i; 
      } 
     } 

dove sum(x) = x * (x + 1)/2;