algorithm - sistemas - algoritmo para los números índices de los coeficientes de la matriz triangular
calculadora de determinantes (7)
Creo que esto debe ser simple, pero no puedo hacerlo bien ...
Tengo una matriz triangular MxM, cuyos coeficientes se almacenan en un vector, fila por fila. Por ejemplo:
M = [ m00 m01 m02 m03 ]
[ m11 m12 m12 ]
[ m22 m23 ]
[ m33 ]
se almacena como
coef[ m00 m01 m02 m03 m11 m12 m13 m22 m23 m33 ]
Ahora estoy buscando un algoritmo no recursivo que me proporcione el tamaño matricial M y el índice de matriz de coeficientes i
unsigned int row_index(i,M)
y
unsigned int column_index(i,M)
del elemento de matriz al que se refiere. Por lo tanto, row_index(9,4) == 3 , column_index(7,4) == 2 etc. si el conteo del índice está basado en cero.
EDITAR: Se han dado varias respuestas usando una iteración. ¿Alguien sabe de expresiones algebraicas?
Aquí hay una solución algebraica (principalmente):
unsigned int row_index( unsigned int i, unsigned int M ){
double m = M;
double row = (-2*m - 1 + sqrt( (4*m*(m+1) - 8*(double)i - 7) )) / -2;
if( row == (double)(int) row ) row -= 1;
return (unsigned int) row;
}
unsigned int column_index( unsigned int i, unsigned int M ){
unsigned int row = row_index( i, M);
return i - M * row + row*(row+1) / 2;
}
EDITAR: fixed row_index ()
Me llevó algo de tiempo entender lo que necesitabas! :)
unsigned int row_index(int i, int m)
{
int iCurrentRow = 0;
int iTotalItems = 0;
for(int j = m; j > 0; j--)
{
iTotalItems += j;
if( (i+1) <= iTotalItems)
return iCurrentRow;
iCurrentRow ++;
}
return -1; // Not checking if "i" can be in a MxM matrix.
}
Lo siento, olvidé la otra función .....
unsigned int column_index(int i, int m)
{
int iTotalItems = 0;
for(int j = m; j > 0; j--)
{
iTotalItems += j;
if( (i+1) <= iTotalItems)
return m - (iTotalItems - i);
}
return -1; // Not checking if "i" can be in a MxM matrix.
}
Puede haber un trazador de líneas ingenioso para estos, pero (menos cualquier comprobación de errores):
unsigned int row_index( unsigned int i, unsigned int M ){
unsigned int row = 0;
unsigned int delta = M - 1;
for( unsigned int x = delta; x < i; x += delta-- ){
row++;
}
return row;
}
unsigned int column_index( unsigned int i, unsigned int M ){
unsigned int row = 0;
unsigned int delta = M - 1;
unsigned int x;
for( x = delta; x < i; x += delta-- ){
row++;
}
return M + i - x - 1;
}
Tiene que ser eso
i == col + row*(M-1)-row*(row-1)/2
Entonces, una forma de encontrar col y row es iterar sobre los posibles valores de la fila:
for(row = 0; row < M; row++){
col = i - row*(M-1)-row*(row-1)/2
if (row <= col < M) return (row,column);
}
Esto es al menos no recursivo, no sé si puedes hacer esto sin iteración.
Como se puede ver a partir de esta y otras respuestas, prácticamente tiene que calcular la fila para calcular la columna, por lo que podría ser inteligente hacer ambas cosas en una función.
One-liners al final de esta respuesta, la explicación sigue :-)
La matriz de coeficientes tiene: M elementos para la primera fila (fila 0, en su indexación), (M-1) para la segunda (fila 1), y así sucesivamente, para un total de M + (M-1) + ... + 1 = M (M + 1) / 2 elementos.
Es un poco más fácil trabajar desde el final, porque la matriz de coeficientes siempre tiene 1 elemento para la última fila (fila M-1), 2 elementos para la segunda fila (fila M-2), 3 elementos para la fila M-3 , y así. Las últimas K filas ocupan las últimas K (K + 1) / 2 posiciones de la matriz de coeficientes.
Ahora suponga que le dan un índice i en la matriz de coeficientes. Hay elementos M (M + 1) / 2-1-i en posiciones mayores que i. Llamar a este número i ''; desea encontrar el mayor k tal que k (k + 1) / 2 ≤ i '' . La forma de este problema es la fuente misma de tu miseria: por lo que puedo ver, no puedes evitar tomar raíces cuadradas :-)
Bueno, hagámoslo de todos modos: k (k + 1) ≤ 2i ''significa (k + 1/2) 2 - 1/4 ≤ 2i'', o equivalentemente k ≤ (sqrt (8i ''+ 1) -1) / 2. Permítanme llamar a la k más grande como K, luego hay K filas que son posteriores (de un total de M filas), por lo que row_index (i, M) es M-1-K. En cuanto al índice de columna, K (K + 1) / 2 elementos del i ''están en filas posteriores, entonces hay j'' = i''-K (K + 1) / 2 elementos posteriores en esta fila (que tiene K + 1 elementos en total), por lo que el índice de columna es K-j ''. [O lo que es lo mismo, esta fila comienza en (K + 1) (K + 2) / 2 desde el final, por lo que solo debemos restar la posición inicial de esta fila de i: i- [M (M + 1) / 2 - (K + 1) (K + 2) / 2]. ¡Es alentador que ambas expresiones den la misma respuesta!]
(Pseudo-) Código [usando ii en lugar de i ''ya que algunos idiomas no permiten variables con nombres como i'' ;-)]:
row_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return M-1-K
column_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
return i - M(M+1)/2 + (K+1)(K+2)/2
Por supuesto, puede convertirlos en frases sencillas sustituyendo las expresiones para ii y K. Es posible que tenga que tener cuidado con los errores de precisión, pero hay formas de encontrar la raíz cuadrada entera que no requiere un cálculo en coma flotante. Además, para citar a Knuth: "Cuidado con los errores en el código anterior, solo he demostrado que es correcto, no lo he probado".
Si me atrevo a hacer una observación adicional: simplemente mantener todos los valores en una matriz M × M tomará como mucho el doble de la memoria, y dependiendo de su problema, el factor de 2 podría ser insignificante en comparación con las mejoras algorítmicas, y podría ser vale la pena negociar el cálculo posiblemente caro de la raíz cuadrada para las expresiones más simples que tendrá.
[Editar: Por cierto, puede probar ese piso ((sqrt (8ii + 1) -1) / 2) = (isqrt (8ii + 1) -1) / 2 donde isqrt (x) = piso (sqrt (x)) es la raíz cuadrada entera, y la división es la división entera (truncamiento, el valor predeterminado en C / C ++ / Java, etc.), por lo que si te preocupan los problemas de precisión, solo tienes que preocuparte por implementar una raíz cuadrada de enteros correctos.]
Pensé un poco y obtuve el siguiente resultado. Tenga en cuenta que obtiene filas y columnas en una sola toma.
Suposiciones: Las filas comienzan en 0. Las columnas comienzan en 0. El índice comienza en 0
Notación
N = tamaño de la matriz (era M en el problema original)
m = Índice del elemento
El código de psuedo es
function ind2subTriu(m,N)
{
d = 0;
i = -1;
while d < m
{
i = i + 1
d = i*(N-1) - i*(i-1)/2
}
i0 = i-1;
j0 = m - i0*(N-1) + i0*(i0-1)/2 + i0 + 1;
return i0,j0
}
Y algún código de octava / matlab
function [i0 j0]= ind2subTriu(m,N)
I = 0:N-2;
d = I*(N-1)-I.*(I-1)/2;
i0 = I(find (d < m,1,''last''));
j0 = m - d(i0+1) + i0 + 1;
¿Qué piensas?
A partir de diciembre de 2011, se agregó un código realmente bueno para hacer esto a GNU / Octave. Potencialmente extenderán sub2ind e ind2sub. El código se puede encontrar por el momento como funciones privadas ind2sub_tril y sub2ind_tril
La explicación de ShreevatsaR es excelente y me ayudó a resolver mi problema. Sin embargo, la explicación y el código provistos para el índice de la columna dan una respuesta ligeramente diferente a la que la pregunta requiere.
Para reiterar, hay j ''= i'' - K (K + 1) / 2 elementos en la fila después de i. Pero la fila, como cualquier otra fila, tiene M elementos. Por lo tanto, el índice de columna (basado en cero) es y = M - 1 - j ''.
El pseudo código correspondiente es:
column_index(i, M):
ii = M(M+1)/2-1-i
K = floor((sqrt(8ii+1)-1)/2)
jj = ii - K(K+1)/2
return M-1-jj
La respuesta dada por ShreevatsaR, K - j '', es el índice de columna al comenzar a contar (con cero) desde la diagonal de la matriz. Por lo tanto, su cálculo da column_index (7,4) = 0 y no, como se especifica en la pregunta, column_index (7,4) = 2.