[C] Determinante de orden N

[BatchianoISpyxolo]

A partir del título de este post ( http://foro.elhacker.net/programacion_cc/determinante_matriz_de_orden_n-t352910.0.html )  me entró la curiosidad de resolverlo de manera dinámica. Y la manera que se me ocurría para un algoritmo sencillo pues es la regla de Laplace o el desarrollo por menores complementarios de manera recursiva:

Código (C) [Seleccionar] Expandir

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define N 4

/* DETERMINANTE DE UNA MATRIZ de orden N - por MAFH */

typedef int ** matriz;

void visualizar_matriz (matriz matrix, int m, int n) {
   int i,j;
   for (i=0; i<m; i++) {
       for(j=0; j<n; j++) {
           printf("%d ", matrix[i][j]);
       }
       printf("\n");
   }
}

matriz generar_matriz (int m, int n) {
   int i;
   matriz temp;
   if ((temp = (matriz) malloc(m*sizeof(int*))) == NULL)
       return NULL;
   for (i=0; i<m; i++)
       if ((temp[i] = (int *)malloc(n*sizeof(int))) == NULL)
           return NULL;
   return temp;
}

matriz copiar_matriz (matriz matrix, int m, int n) {
   int i,j;
   matriz temp = (matriz) generar_matriz(m,n);
   if (temp != NULL) {
for (i=0; i<m; i++)
for (j=0; j<n; j++)
temp[i][j] = matrix[i][j];
   }
   return temp;
}

void liberar_matriz (matriz matrix, int m) {
   int i;
   for (i=0; i<m; i++)
       free(matrix[i]);
   free(matrix);
}

void rellenar_matriz (matriz matrix, int m, int n) {
   int i,j;
   for (i=0; i<m; i++)
       for(j=0; j<n; j++) {
           printf("Valor de matrix[%d,%d] = ", i, j);
           scanf("%d", &(matrix[i][j]));
       }
}

matriz adjunto_matriz (matriz matrix, int fila, int columna, int n) {
   matriz adjunto = (matriz) generar_matriz(n-1,n-1);
   if (adjunto != NULL) {
int i, j, k=0, l=0;
for (i=0; i<n; i++)
for (j=0; j<n; j++) {
if ((i != fila) && (j != columna)) {
adjunto[k][l] = matrix[i][j];
if (++l == n-1) {
l=0;
k++;
}
}
}
   }
   return adjunto;
}

int determinante (matriz matrix, int n) {
   if (n == 1) {
       return matrix[0][0];
   } else {
       int j;
       int res = 0;
       for (j=0; j<n; j++){
           matriz adjunto = (matriz) adjunto_matriz(matrix, 0, j, n);
           if (adjunto == NULL) exit(1);
           res += pow(-1, (j%2))*matrix[0][j]*determinante(adjunto, n-1);
           liberar_matriz(adjunto,n-1);
       }
       return res;
   }
}


int main (int argc, char ** argv) {
   matriz m = (matriz) generar_matriz(N,N);
   rellenar_matriz(m,N,N);
   visualizar_matriz(m,N,N);
   printf("|M| = %d\n", determinante(m,N));
   liberar_matriz(m,N);
   return 0;
}


Aunque tenemos la constante N para el orden de la matriz, podemos utilizar una variable para que el usuario introduzca el orden, evidentemente.

Una ejecución del código con Valgrind:

pyxolo@ubuntu:~/Escritorio$ gcc -o det determinanteN.c -lm
pyxolo@ubuntu:~/Escritorio$ valgrind ./det -all
==4938== Memcheck, a memory error detector
==4938== Copyright (C) 2002-2011, and GNU GPL'd, by Julian Seward et al.
==4938== Using Valgrind-3.7.0 and LibVEX; rerun with -h for copyright info
==4938== Command: ./det -all
==4938==
Valor de matrix[0,0] = 2
Valor de matrix[0,1] = 3
Valor de matrix[0,2] = -4
Valor de matrix[0,3] = 2
Valor de matrix[1,0] = 9
Valor de matrix[1,1] = 11
Valor de matrix[1,2] = 0
Valor de matrix[1,3] = 3
Valor de matrix[2,0] = 2
Valor de matrix[2,1] = -4
Valor de matrix[2,2] = -5
Valor de matrix[2,3] = -6
Valor de matrix[3,0] = 21
Valor de matrix[3,1] = 100
Valor de matrix[3,2] = 2
Valor de matrix[3,3] = 3
2 3 -4 2
9 11 0 3
2 -4 -5 -6
21 100 2 3
|M| = -23240
==4938==
==4938== HEAP SUMMARY:
==4938==     in use at exit: 0 bytes in 0 blocks
==4938==   total heap usage: 105 allocs, 105 frees, 752 bytes allocated
==4938==
==4938== All heap blocks were freed -- no leaks are possible
==4938==
==4938== For counts of detected and suppressed errors, rerun with: -v
==4938== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Conclusión del desarrollo por menores:

Orden 1:
1 de orden 1
no llamadas recursivas

Orden 2:
2 de orden 1
2 = 2 llamadas recursivas

Orden 3:
3 de orden 2
2 de orden 1
3*2 = 6 llamadas recursivas

Orden 4:
4 de orden 3
3 de orden 2
2 de orden 1
4*3*2 = 24 llamadas recursivas

Orden 5:
5 de orden 4
4 de orden 3
3 de orden 2
2 de orden 1
5*4*3*2 = 120 llamadas recursivas

Orden n:
n de orden n-1
n-1 de orden n-2
.... de orden ...
3 de orden 2
2 de orden 1
n*(n-1)*(n-2)*(n-3)*...*(n-n+1) = (productorio desde i=n hasta 2 de i) = n! llamadas recursivas

Como conclusión a los resultados expuestos obtenemos que el número de llamadas recursivas que se realizan viene dado por:

Nº llamadas recursivas = Permutaciones(Orden) = Orden!

Como bien había dicho ghastlyX en respuesta al tema arriba enlazado.



Edit:

He tratado de lanzar el código con un determinante de orden 13 y evidentemente "no terminaba"...
Nº llamadas recursivas = P(13) = 13! = 6227020800

T(n) es exponencial y encima con los alojos y desalojos de memoria... Para morirse xD

Por otra parte, convendría generar los adjuntos con la misma matriz que se usa o de alguna manera sin generar otra matriz de tamaño n-1 para cada adjunto ._.

[amchacon]

Buena idea, yo hize también un algoritmo recursivo pero en C++... Andara por algun lugar de este foro.

El determinante es una operacion complej, hacer un determinante de 20x20 puede trardar semanas (y me quedo corto).

[leosansan]

El determinante es una operacion complej, hacer un determinante de 20x20 puede trardar semanas (y me quedo corto).

Es que el sistema que utilizan es de "fuerza bruta".

Para hacerlo razonable habría que usar Gauss con/sin pivotes.

Saluditos!, ....

[BatchianoISpyxolo]

Es que el sistema que utilizan es de "fuerza bruta".

Para hacerlo razonable habría que usar Gauss con/sin pivotes.

Saluditos!, ....

No, ya, ya. diagonalizar la matriz para obtener la solución con el producto de los elementos de la diagonal principal xD Pero para diagonalizar la matriz... xD No sabría como hacerlo de forma eficiente. Aunque bueno, debería tratar de pensarlo para afirmar eso xD

[leosansan]

.......................................
Pero para diagonalizar la matriz... xD No sabría como hacerlo de forma eficiente.
........................................

No es tan complicado, al menos sin pivote. Un ejemplo:

Código (cpp) [Seleccionar] Expandir


/* Función para triangularizar una matriz */
/************************************************/
int triang(int N, double **a, double *b)
{
    int i, j, k, error;
    double fac;
    for (k=0; k<N-1; k++)
        for (i=k+1; i<N; i++)
            {
                if (fabs(a[k][k])<EPS) return -1;
                fac=-a[i][k]/a[k][k];
                 for (j=k; j<N; j++)
                    {
                        a[i][j]+=a[k][j]*fac;
                    }
                b[i]=b[i]+b[k]*fac;
               
            }return 1;
}
/* Función para resolver un sistema triangular superior */
/************************************************/


Saluditos!. ...