Линейный индекс верхней треугольной матрицы
Если у меня есть верхняя треугольная часть матрицы, смещенная выше диагонали, сохраненная в виде линейного массива, как (i,j) индексы матричного элемента извлекаются из линейного индекса массива?
Например, линейный массив [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 это хранилище для матрицы
0 a0 a1 a2 a3
0 0 a4 a5 a6
0 0 0 a7 a8
0 0 0 0 a9
0 0 0 0 0
И мы хотим знать индекс (i, j) в массиве, соответствующий смещению в линейной матрице, без рекурсии.
Подходящий результат, k2ij(int k, int n) -> (int, int) удовлетворит, например,
k2ij(k=0, n=5) = (0, 1)
k2ij(k=1, n=5) = (0, 2)
k2ij(k=2, n=5) = (0, 3)
k2ij(k=3, n=5) = (0, 4)
k2ij(k=4, n=5) = (1, 2)
k2ij(k=5, n=5) = (1, 3)
[etc]
Решение
Уравнения, идущие от линейного индекса к (i,j) Индекс
i = n - 2 - floor(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5)
j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2
Обратная операция, от (i,j) индекс на линейный индекс
k = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1
Проверьте в Python с помощью:
from numpy import triu_indices, sqrt
n = 10
for k in range(n*(n-1)/2):
i = n - 2 - int(sqrt(-8*k + 4*n*(n-1)-7)/2.0 - 0.5)
j = k + i + 1 - n*(n-1)/2 + (n-i)*((n-i)-1)/2
assert np.triu_indices(n, k=1)[0][k] == i
assert np.triu_indices(n, k=1)[1][k] == j
for i in range(n):
for j in range(i+1, n):
k = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1
assert triu_indices(n, k=1)[0][k] == i
assert triu_indices(n, k=1)[1][k] == j
Другие решения
Во-первых, давайте изменим нумерацию [k] в обратном порядке. Мы получим:
0 a9 a8 a7 a6
0 0 a5 a4 a3
0 0 0 a2 a1
0 0 0 0 a0
0 0 0 0 0
Тогда k2ij (k, n) станет k2ij (n — k, n).
Теперь вопрос в том, как вычислить k2ij (k, n) в этой новой матрице. Последовательность 0, 2, 5, 9 (индексы диагональных элементов) соответствует треугольные числа (после вычитания 1): a [n — i, n + 1 — i] = Ti — 1. Ti = i * (i + 1) / 2, поэтому, если мы знаем Ti, легко решить это уравнение и получить i (см. формулу в связанной статье в вики, раздел «Треугольные корни и тесты на треугольные числа»). Если k + 1 не является точно треугольным числом, формула все равно даст вам полезный результат: после округления вниз вы получите наибольшее значение i, для которого Ti <= k, это значение i соответствует индексу строки (считая снизу), в котором находится a [k]. Чтобы получить столбец (считая справа), нужно просто рассчитать значение Ti и вычесть его: j = k + 1 — Ti. Чтобы было ясно, это не совсем i и j из вашей проблемы, вам нужно «перевернуть» их.
Я не написал точную формулу, но я надеюсь, что вы поняли идею, и теперь будет тривиально найти ее после выполнения некоторых скучных, но простых вычислений.
Ниже приведен пример использования Matlab, который можно легко перенести на другой язык, например C ++. Здесь мы предполагаем, что матрица имеет размер m * m, ind — индекс в линейном массиве. Единственное отличие состоит в том, что здесь мы подсчитываем нижнюю треугольную часть матрицы столбец за столбцом, что аналогично вашему случаю (считая верхнюю треугольную часть строка за строкой).
function z= ind2lTra (ind, m)
rvLinear = (m*(m-1))/2-ind;
k = floor( (sqrt(1+8*rvLinear)-1)/2 );
j= rvLinear - k*(k+1)/2;
z=[m-j, m-(k+1)];
В питоне:
def k2ij(k, n):
rows = 0
for t, cols in enumerate(xrange(n - 1, -1, -1)):
rows += cols
if k in xrange(rows):
return (t, n - (rows - k))
return None