Calculo de determinantes en Haskell

Archivado
¡Hola!

Estoy haciendo un pequeño programa en Haskell sobre matrices (multiplicacion entre ellas, con escalares, sumas, restas, diagonales principales y secundarias, triangulos y demas), y me he propuesto sacar el calculo de las matrices inversas.

Para ello necesito calcular los adjuntos de la matriz, algo que no parece demasiado complicado, salvo por el pequeño inconveniente de calcular los determinantes. Esta tirado, de hecho, calcularme el determinante de tamaño 2 (el de 3 va a ser un poco mas complicado, pero lo veo bastante asequible). Pero claro, yo necesito un metodo general para calcular determinantes, sean tamaño 2, 3 o 5.

¿Alguna idea de como afrontar el problema? Por ahora he pensado representar los determinantes como las matrices (me he roto la cabeza XD), que son listas de listas de tipo Num, pero no se me ocurre ningun algoritmo para calcular determinantes de tamaño mayor a 3. Y ya si alguien me da una idea buena con funciones de orden superior, la repanocha XD

Resumiendo: Necesito una idea para desarrollar un algoritmo sobre esto.

Gracias ;)
Los determinantes de orden mayor a N se calculan en base a determinates de orden N-1, al final acabarás con determinates de orden 2 o directamente con un término.

Vamos que lo hagas recursivamente ,que tratandose de haskell tiene mucho sentido.
La manera mas facil de calcular un determinante es por gauss. Es decir calculas la matriz triangular superior equivalente por gauss y el resultado de la diagonal es el determinante, no es el metodo ideal pero va bien.
Se me habia olvidado y por eso no puse el codigo. Ya lo tengo solucionado, de la forma que me decia wah wah (gracias!) aunque tratandose de uno de mis primeros codigos en Haskell me temo que no esta demasiado bien hecho (y de eficiencia...en fin, creo que me sale coste m*n siendo m numero de filas y n numero de columnas, pero tampoco se si se podra calcular en tiempo menor).


Este primero es completamente funcional.

--Dado un determinante de tamaño N, calcula su resultado
det :: Num a => [[a]] -> a
det [] = 0
det (xs:xss)
| (esCuadrada (xs:xss) && (nColumnas (xs:xss) == 2)) = det2 (xs:xss)
| (esCuadrada (xs:xss) && (nColumnas (xs:xss) > 0))  = solucionaDet (xs:xss) 0 0 (nColumnas (xs:xss) - 1)  --es (-1) porque vamos a comparar con el 0 anterior (pos)
| otherwise = 0  -- La matriz (determinante) no es cuadrada


--Dado un determinante de tamaño N>2 y un entero, resuelve un determinante
--Si y es 0, entonces se multiplica por 1
--Si y es 1, entonces se multiplica por (-1)
--pos indica la posicion del elemento sobre el que se calcula el determinante de tamaño N-1
--z es el numero de columnas o filas, es indiferente porque nos hemos asegurado que es cuadrado en el helper.

solucionaDet :: Num a => [[a]] -> Int -> Int -> Int -> a
solucionaDet [] y pos z = 0

solucionaDet (xs:xss) 0 pos z --                                    --Caso de elemento que suma
| z == 1 = det2 (xs:xss)
| pos == z  = valor * (det(adjDet (xs:xss) pos))
| otherwise = valor * (det(adjDet (xs:xss) pos)) + solucionaDet (xs:xss) 1 (pos+1) z
   where valor = (map head (xs:xss))!!pos                                         

solucionaDet (xs:xss) 1 pos z                                    --Caso de elemento que resta
| z == 1 = det2 (xs:xss)
   | pos == z  = ((-1) * valor * (det(adjDet (xs:xss) pos)))
   | otherwise = ((-1) * valor * (det(adjDet (xs:xss) pos))) + solucionaDet (xs:xss) 0 (pos+1) z
   where valor = (map head (xs:xss))!!pos 




La otra idea que tenia, parecida a esta, era usando la "y" como elemento a multiplicar en vez de como "codigo/codificacion" para saber el valor por el cual multiplicar.

El codigo resultante es un poco chapucerillo porque intente hacerlo reaprovechando codigo y no se que hacia mal que no me inferia para cualquier tipo numerico, asi que lo dejo a modo curiosidad y por si alguien se le ocurre como solucionarle, pero ya advierto que este no funciona.
--Dado un determinante de tamaño N, calcula su resultado
det :: Num a =>  [[a]] -> a
det [] = 0
det (xs:xss)
| (esCuadrada (xs:xss) && (nColumnas (xs:xss) == 2)) = det2 (xs:xss)
| (esCuadrada (xs:xss) && (nColumnas (xs:xss) > 0))  = solucionaDet (xs:xss) 1 0 (nColumnas (xs:xss) - 1)  --es (-1) porque vamos a comparar con el 0 anterior (pos)
| otherwise = 0  -- La matriz (determinante) no es cuadrada


--Dado un determinante de tamaño N>2 y un entero, resuelve un determinante
--Y es el valor por el cual hay que multiplicar el resultado, 1 ó -1, ya sea caso de subdeterminante que suma o que resta.
--pos indica la posicion del elemento sobre el que se calcula el determinante de tamaño N-1
--z es el numero de columnas

solucionaDet :: Num a => [[a]] -> Int -> Int -> Int -> a
solucionaDet [] y pos z = 0

solucionaDet (xs:xss) y pos z
| z == 1 = det2 (xs:xss)
| pos == z  = y * valor * (det(adjDet (xs:xss) pos))
| otherwise = y * valor * (det(adjDet (xs:xss) pos)) + solucionaDet (xs:xss) (-y) (pos+1) z
   where valor = (map head (xs:xss))!!pos                                         


Ya digo que este segundo no funciona por definir explicitamente un numero "a" como entero, asi que si a alguien le apetece arreglarlo, adelante ;)

Creo que no hace falta que ponga el codigo de la funcion adjDet (que como su propio nombre indica, calcula el adjunto de una matriz/determinante siempre sobre su primera columna) y el de esCuadrada y nColumnas es TAAAN sencillo que si alguien no lo sabe sacar no merece usar mi codigo XD

En fin, que espero que a alguien le sirva, y si lo mejora -cosa no muy complicada, creo- le agradeceria que lo pusiese. Un saludo!
3 respuestas
Archivado
Volver a General