将2D上三角形和下三角形中的元素映射到线性结构中。

Question

我有一个维度为NxN的矩阵M，其中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;
}

- Matthieu N.

---

三角矩阵中元素的数量不是N²/2，而是(N²+N)/2。 - Fred Foo

Answer 1

为了实现相反的方向，这正是我需要的:

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

- Micah Chambers

---

谢谢，这正是我所需要的。在GPU上性能比我想出来的要好得多：int c = element; int r = 0; while (c - (r+1) >= 0) { r++; c -= r; } - Devin Lane

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。你需要 (size+1)*size/2 元素空间来完成此操作。

- Gunther Piez

---

这个公式是不正确的。作者要求的是上三角矩阵，而不是下三角矩阵。 - Viktor

@ViktorFonic 最后一句提供了上三角形的公式。将"If x>y"解读为"如果你需要上三角形"。 - Gunther Piez

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;

- Viktor