2

我正在寻找一种可以遍历网格并将其转换为具有新顺序索引的另一个网格的算法。

基本上，给定一个大小为 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
4

2 回答 2

2

以下似乎对我有用：

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。

编辑：

您可以获得索引i和j给定index的如下：

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;
}
于 2013-03-02T22:59:38.337 回答
2

让我们定义起始网格 NxM 中每个网格元素 (i,j) 的“序数位置”O(i,j)，即函数 (i,j) -> i*N + j。

现在对于小于 O(i,j) 的最大三角形数，将其称为 T == (k(k+1)/2 对于某个 k，我们的 (i,j) 的新网格位置将是： (i, j) -> ( O(i,j) - T, k + T - O(i,j) )

现在替换 O(i,j) 和 T 得到：

(i,j) -> ( i*N + j - k(k+1)/2, k + (k+1)(k+2)/2 - i*N + j)

= ( i*N + j - k(k+1)/2, (k+1)(k+2)/2 - i*N + j)

这是我现在所能得到的。

更新： 再次注意 k 是三角形数 T == k(k+1)/2 的边长。

于 2013-03-02T21:25:40.423 回答