Верхняя треугольная матрица линейного индекса

Если у меня есть верхняя треугольная часть матрицы, смещенная над диагональю, хранящаяся в виде линейного массива, как можно выделить индексы (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]

Ответ 1

Уравнения, идущие от линейного индекса до индекса (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

Ответ 2

Сначала перенумеруем [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 + 1)/2, поэтому, если мы знаем Ti, легко решить это уравнение и получить я (см. формулу в связанной статье wiki, раздел "Треугольный корней и тестов для треугольных чисел" ). Если k + 1 не является точно треугольным числом, формула по-прежнему даст вам полезный результат: после округления его вы получите максимальное значение i, для которого Ti <= k, это значение я соответствует индекс строки (считая снизу), в котором находится [k]. Чтобы получить столбец (считая справа), вы должны просто вычислить значение Ti и вычесть его: j = k + 1 - Ti. Чтобы быть ясными, они не являются чрезмерно я и j из вашей проблемы, вам нужно "перевернуть" их.

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

Ответ 3

Ниже приведена интерпретация в Matlab, которая может быть легко перенесена на другой язык, например С++. Здесь мы предполагаем, что матрица имеет размер 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)];

Ответ 4

В python:

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