c# - 如何迭代网格算法

Question

我正在寻找一种算法，可以迭代一个网格并将其转换为另一个网格，并按新的顺序索引。

基本上，给定一个大小为 n*m 的网格:

1_1 1_2 1_3 ... 1_n
2_1 2_2 2_3 ... 2_n
.
.
.
m_1 m_2 m_3 ... m_m

如何将其转换为:

1_1 1_2 1_4 ...
1_3 1_5 ...
1_6 ...
...
.
.
.

假设您迭代第一个网格，在顶行中从左到右，然后 从左到右在第二行，一直到从左到右在底行。

基本上，我将元素插入上三角形。

另一个问题是，如何仅通过知道 n 和 m 来计算出用于存储三角形的网格的长度和宽度？ 有公式吗？

例如，5*6的网格，变为8*7...

1  2  3  4  5
6  7  8  9  10
11 12 13 14 15
16 17 18 19 20
21 22 23 24 25
26 27 28 29 30

变成:

 1  2  4  7  11 16 22 29
 3  5  8  12 17 23 30
 6  9  13 18 24
 10 14 19 25
 15 20 26
 21 27
 28

Answer 1

以下似乎对我有用:

public static T[,] ConvertToUpperTriangle<T>(T[,] arr)
{
    // calculate the dimensions
    int elements = arr.GetLength(0) * arr.GetLength(1);

    double rows = 0.5 * (Math.Sqrt(8 * elements + 1) - 1);

    int newHeight = (int)rows;
    int newWidth = (int)Math.Ceiling(rows);

    // create the new array
    var arr2 = new T[newHeight, newWidth];

    int j = 0;
    int i = 0;
    foreach (T element in arr)
    {
        arr2[j, i] = element;
        i--;
        j++;
        if (i < 0)
        {
            i = j;
            j = 0;
        }
    }

    return arr2;
}

0.5 * (Math.Sqrt(8 * elements + 1) - 1) 来自运行 sum from 1 to n of n，然后 solve a = 0.5 * n * (n + 1) for n 到 Wolfram Alpha .

编辑:

您可以获取给定index的索引i和j，如下所示:

int rows = (int)(0.5 * (Math.Sqrt(8 * index + 1) - 1));

int bottomLeft = (int)(0.5 * rows * (rows + 1));
int difference = index - bottomLeft;

int i;
int j;

if (bottomLeft == index)
{
    i = 0;
    j = rows - 1;
}
else
{
    i = rows + 1 - difference;
    j = difference - 1;
}