Предоставление элемента из нижней/верхней треугольной матрицы

Question

У меня верхняя треугольная часть матрицы с основной диагональю, хранящейся в виде линейного массива, как можно отличить индексы (i, j) матричного элемента от линейного индекс массива?

Например линейный массив: [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9, a10] является для хранения матрицы

a0 a1 a2 a3 
0 a4 a5 a6 
0 0 a7 a8 
0 0 0 a10 

Я нашел решение этой проблемы, но без главной диагонали, которая:

index = (n*(n-1)/2) - (n-i)*((n-i)-1)/2 + j - i - 1 

И решения для та же проблема, но для нижней треугольной матрицы с диагональю:

index = ((i + 1) * i/2 + i). 

С уважением,

Answer 1

Мое решение может быть эквивалентно your’s, я не проверил:

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

Вот полный тест Python для него. Я использовал Python, потому что Numpy имеет triu_indices, что дает верхние треугольные индексы.

import numpy as np 

def mksquare(N): 
    """Make a square N by N matrix containing 0 .. N*N-1""" 
    return np.arange(N * N).reshape(N, N) 

def mkinds(N): 
    """Return all triu indexes for N by N matrix""" 
    return [(i,j) for i in range(N) for j in range(N) if i <= j] 

def ij2linear(i, j, N): 
    """Convert (i,j) 2D index to linear triu index for N by N array""" 
    return N * i - ((i - 1) * i) // 2 + (j - i) 

def test(N): 
    """Make sure my `mkinds` works for given N""" 
    arr = mksquare(N) 
    vec = arr[np.triu_indices(N)] 

    inds = mkinds(N) 
    expected = [arr[i, j] for (i, j) in inds] 

    actual = [vec[ij2linear(i, j, N)] for (i, j) in inds] 

    return np.all(np.equal(actual, expected)) 

"""Run `test` for a bunch of `N`s and make sure they're all right""" 
print(all(map(test, range(2, 20)))) 
# prints True 

Стоит сообщение в блоге, объясняющее, как прийти к такому выводу, но пока это будет сделано.

Answer 2

Я понял ответ! Это:

index = (n*(n+1)/2) - (n-i)*((n-i)+1)/2 + j - i