c++ - transpuesta - Matriz triangular superior índice lineal

matriz triangular superior java

Question

Si tengo la parte triangular superior de una matriz, desplazada por encima de la diagonal, almacenada como una matriz lineal, ¿cómo pueden extraerse los índices (i,j) de un elemento de matriz del índice lineal de la matriz?

Por ejemplo, la matriz lineal [a0, a1, a2, a3, a4, a5, a6, a7, a8, a9 es almacenamiento para la matriz

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

Y queremos saber el índice (i, j) en la matriz correspondiente a un desplazamiento en la matriz lineal, sin recursión.

Un resultado adecuado, k2ij(int k, int n) -> (int, int) satisfaría, por ejemplo

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]

Answer 1

En 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

Answer 2

La siguiente es una implementación en matlab, que se puede transferir fácilmente a otro idioma, como C ++. Aquí, suponemos que la matriz tiene un tamaño m * m, ind es el índice en la matriz lineal. Lo único diferente es que aquí, contamos la parte triangular inferior de la matriz columna por columna, que es análoga a su caso (contando la fila triangular superior fila por fila).

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)];

Answer 3

Las ecuaciones que van del índice lineal al índice (i,j) son

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

La operación inversa, de (i,j) índice a índice lineal es

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

Verificar en Python con:

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

Answer 4

Primero, vamos a renumerar a [k] en orden opuesto. Nosotros recibiremos:

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

Entonces k2ij (k, n) se convertirá en k2ij (n - k, n).

Ahora, la pregunta es, cómo calcular k2ij (k, n) en esta nueva matriz. La secuencia 0, 2, 5, 9 (índices de elementos diagonales) corresponde a números triangulares (después de restar 1): a [n - i, n + 1 - i] = Ti - 1. Ti = i * (i + 1 ) / 2, por lo que si conocemos Ti, es fácil resolver esta ecuación y obtener i (consulte la fórmula en el artículo wiki vinculado, sección "Raíces triangulares y pruebas de números triangulares"). Si k + 1 no es exactamente un número triangular, la fórmula aún le dará un resultado útil: después de redondearlo, obtendrá el valor más alto de i, para el cual Ti <= k, este valor de i corresponde al Índice de fila (contando desde abajo), en el que se encuentra un [k]. Para obtener la columna (contando desde la derecha), simplemente debe calcular el valor de Ti y restarlo: j = k + 1 - Ti. Para que quede claro, no se trata exactamente de su problema, debe "voltearlos".

No escribí la fórmula exacta, pero espero que se te haya ocurrido la idea, y ahora será trivial encontrarla después de realizar algunos cálculos aburridos pero simples.