Как преобразовать индексы треугольной матрицы в строку, координаты столбца?

Question

У меня есть idxs:

1,2,3,4,5,6,7,8,9,10,11,12,13,14,15...ect.

которые являются индексами узлов в матрице (включая диагональные элементы):

1
2  3
4  5  6
7  8  9  10
11 12 13 14 15
16 17 18 19 20 21
etc....

и мне нужно получить координаты i, j из этих индексов:

1,1
2,1 2,2
3,1 3,2 3,3
4,1 4,2 4,3 4,4
5,1 5,2 5,3 5,4 5,5
6,1 6,2 6,3 6,4 6,5 6,6
etc..

когда мне нужно вычислить координаты, у меня есть только один idx и я не могу получить доступ к другим.

0

Решение

Других решений пока нет …

Accepted Answer

Совсем не оптимизировано:

int j = idx;
int i = 1;

while(j > i) {
j -= i++;
}

Оптимизировано:

int i = std::ceil(std::sqrt(2 * idx + 0.25) - 0.5);
int j = idx - (i-1) * i / 2;

А вот и демонстрация:

Вы ищете я такой, что:

sumRange(1, i-1) < idx && idx <= sumRange(1, i)

когда sumRange (min, max) суммирует целые числа между min и max, оба включаются.
Но так как вы знаете, что:

sumRange(1, i) = i * (i + 1) / 2

Тогда у вас есть:

idx <= i * (i+1) / 2
=> 2 * idx <= i * (i+1)
=> 2 * idx <= i² + i + 1/4 - 1/4
=> 2 * idx + 1/4 <= (i + 1/2)²
=> sqrt(2 * idx + 1/4) - 1/2 <= i

4