将二维上三角和下三角中的元素映射为线性结构

I have a matrix M which is of NxN dimensions, where M(i,j) = M(j,i)

我有一个矩阵M它是NxN维的，其中M(I,j) = M(j, I)

I would like to represent this structure as a (N²+N)/2 linear array K, to save space. My problem is coming up with the formula that will map a M(min(i,j),min(i,j)) into a range [0,(N^2)/2)

我想这种结构表示为一个线性阵列(N²+ N)/ 2 K,以节省空间。我的问题是公式,将地图M(min(i,j),最小值(i,j))在区间[0,(N ^ 2)/ 2)

Below is a mapping of a 3x3 matrix with indexes for K linear array, the X means those cells don't exist and instead their transpose is to be used:

下面是一个3x3矩阵与K线性数组的索引的映射，X表示这些细胞不存在，而它们的转置将被使用:

0123
X456
XX78
XXX9

Here is a 7x7 matrix with indexes for the K linear array

这是一个有K个线性数组索引的7x7矩阵

     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

at the moment I have the following

目前我有以下几点

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;
}

3 个解决方案

#1

To go the opposite direction which is what I needed:

我需要走相反的方向:

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

#2

Assuming y >= x, you could use a "mapping" like

假设y >= x，可以使用“映射”。

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

which would produce

这将产生

 0

 1   2

 3   4   5

 6   7   8   9

10  11  12  13  14

If x>y, just swap x and y. You need (size+1)*size/2 elements space for this.

如果x>y，交换x和y，你需要(size+1)*size/2元素空间。

#3

-3

Here's the correct mapping:

这是正确的映射:

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

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

其中sum(x) = x * (x + 1) / 2;

#1