Как выполнить итерацию по алгоритму сетки

Question

Я ищу алгоритм, который может проходить через сетку и преобразовывать ее в другую сетку с индексами в новом порядке.

В принципе, учитывая сетку размера Н * м:

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

Давайте определим "порядковое положение" O (I, j) каждого элемента решетки (i, j) в стартовой сетке NxM, которая является функцией (i, j) -> i * N + j.

Теперь для наибольшего треугольного числа, меньшего, чем O (i, j), назовем его T == (k (k + 1)/2 для некоторого k, новая позиция сетки для нашего (i, j) будет : (I, J) -> (О (I, J) - T, K + T - O (I, J))

---

Теперь заменить O (I, J) и Т, чтобы получить :

(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)

---

Это насколько я могу получить его сейчас.

Обновление: Отметим еще раз, что к является стороной длины для числа triangualr Т == к (к + 1)/2.

Answer 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.

Edit:

Вы можете получить индексы 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; 
}