elementos Mapping en triángulo superior 2D y triángulo inferior a la estructura lineal

Question

I tienen un M matriz que es de dimensiones NxN, donde M (i, j) = M (j, i)

Me gustaría representar esta estructura como una matriz lineal K (N² + N)/2, para ahorrar espacio. Mi problema es encontrar la fórmula que mapeará una M (min (i, j), min (i, j)) en un rango [0, (N^2)/2)

A continuación se muestra un mapeo de una matriz 3x3 con índices para K matriz lineal, el X significa no existen esas células y en lugar de su transpuesta es para ser utilizado:

X456 
XX78 
XXX9 

Aquí es una matriz 7x7 con índices de la matriz lineal 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 

en el momento tengo los siguientes

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

Asumiendo y> = x, se puede utilizar un "mapeo" como

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

que produciría

0 

1 2 

3 4 5 

6 7 8 9 

10 11 12 13 14 

Si x> y, sólo cambio x e y. Necesitas (tamaño + 1) * tamaño/2 elementos de espacio para esto.

Answer 2

ir en la dirección opuesta que es lo que necesitaba:

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

Answer 3

Así es la asignación correcta:

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

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