algoritmo para números de índice de matriz triangular coeficientes

Question

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 da para el tamaño de la matriz M y el coeficiente de índice de matriz 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 recuento de índices está basado en cero.

EDITAR: Se han dado varias respuestas utilizando una iteración. ¿Alguien sabe de expresiones algebraicas?

Answer 1

Aquí es una solución (en su mayoría) algebraica:

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; 
} 

EDIT: fijo ROW_INDEX()

Answer 2

¡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 sentimos 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. 
} 

Answer 3

Tiene que ser que

i == col + row*(M-1)-row*(row-1)/2 

Así que una manera de encontrar la col y la fila es para repetir valores posibles 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 esta en lea st no recursivo, no sé si puedes hacer esto sin iteración.

Como se puede ver en esta y otras respuestas, casi tiene que calcular la fila para calcular la columna, por lo que podría ser inteligente hacer ambas cosas en una función.

Answer 4

Puede haber un inteligente un trazador de líneas para estos, pero (comprobación menos cualquier error):

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; 
} 

Answer 5

de una sola línea al final de esta respuesta, la explicación siguiente :-)

el co array eficiente tiene: M elementos para la primera fila (fila 0, en su indexación), (M-1) para el segundo (fila 1), y así sucesivamente, para un total de M + (M-1) + & hellip; + 1 = M (M + 1)/2 elementos.

Es un poco más fácil trabajar desde el final, debido a que la matriz de coeficiente de siempre tiene 1 elemento para la última fila (fila M-1), 2 elementos para la segunda última fila (fila M-2), 3 elementos para la fila M-3, y así sucesivamente.Las últimas K filas ocupan las últimas K (K + 1)/2 posiciones de la matriz de coeficientes.

Supongamos que se le asigna 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 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) - 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 dan la misma respuesta]

(pseudo) Código [ii utilizando en lugar de i 'como 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 que puede convertirlos en frases sencillas sustituyendo las expresiones para ii y K. Puede que tenga cuidado con los errores de precisión, pero hay formas de encontrar la raíz cuadrada entera que no requiere cálculo de punto 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 un M × matriz M tomará como máximo el doble de memoria, y dependiendo de su problema, el factor de 2 podría ser insignificante en comparación con las mejoras algorítmicas , y valdría la pena comerciar con 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 una raíz cuadrada entera, y la división es una división entera (truncamiento, el valor predeterminado en C/C++/Java, etc.) - por lo que si le preocupan los problemas de precisión, solo tiene que preocuparse por implementar un número entero correcto raíz cuadrada.]

Answer 6

Pensé un poco y obtuve el siguiente resultado. Tenga en cuenta que obtiene filas y columnas en una sola toma.

Supuestos: Filas comienzan un 0. Columnas comienzan en 0. índice de inicio a 0

Notación

N = tamaño de la matriz (M era en el problema original)

m = Índice de la elemento

El pseudo código 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 un 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é opinas?

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

Answer 7

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 la columna al comenzar a contar (con cero) de 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.