Отображение элементов в 2D верхнем треугольнике и нижнем треугольнике в линейную структуру

Question

У меня есть матрица M, которая имеет размеры NxN, где M (i, j) = M (j, i)

Я бы хотела представить эту структуру как (N² + N) / 2.линейный массив K, для экономии места.Моя проблема состоит в том, чтобы придумать формулу, которая отображает M (min (i, j), min (i, j)) в диапазон [0, (N ^ 2) / 2)

Нижеотображение матрицы 3x3 с индексами для линейного массива K, X означает, что эти ячейки не существуют, и вместо этого следует использовать их транспонирование:

0123
X456
XX78
XXX9

Вот матрица 7x7 с индексами для 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

на данный момент у меня есть следующее

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

Чтобы пойти в противоположном направлении, это то, что мне нужно:

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

Answer 2

Предполагая, что y> = x, вы можете использовать «отображение», такое как

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

, которое даст

 0

 1   2

 3   4   5

 6   7   8   9

10  11  12  13  14

Если x> y, просто поменяйте местами x и y.Для этого вам нужно (размер + 1) * размер / 2 элемента.

Answer 3

Вот правильное отображение:

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

где sum(x) = x * (x + 1) / 2;