Privacidad: Recuerde que la información escrita en los foros de programación es 100% pública y que su ip será registrada asociada a su mensaje. Si encuentra un mensaje fuera de lugar, por favor, notifiquelo para su revisión y eliminación.
Cómo mejorar algoritmo de Permutaciones
Enviado por nacho@linux el día 26 de mayo de 2006
Hola estimados...
nuevamente necesito su ayuda, les cuento:
estoy haciendo el programa de los cuadrados mágicos, al cual se le ingresan los datos mediante un archivo, y tienes que disponerlos dentro del cuadrado y probar si es que es mágico o no... O sea, debo probar todas las permutaciones posibles para esos elementos, y ver si calzan.
Ya tengo listo el algoritmo de las permutaciones, y es realmente rápido en matrices de 3x3... el problema es cuando aumentamos el orden, ya que es O(n!)
de 3x3 = 9! = 362.880 permutaciones
de 4x4 = 16! = 20.922.789.888.000 permutaciones
de 5x5 = 25! = un montón de permutaciones ; )
Lo que quiero hacer es una especie de Branch & Bound, pero el problema es que no sé cómo implementarlo; es bastante simple:
- si es que una fila no suma la constante mágica (suma total / columnas), entonces puedo dejar de considerar los números siguientes de esa fila, y así ahorrarme todas esas permutaciones... es super eficiente, por ejemplo, si tengo un cuadrado de 3x3, y la primera fila tiene: 2 5 3, eso suma 10, y debería ser 15 (si es que los números son correlativos desde el 1), así que puedo descartar todas las combinaciones que salen del comienzo con 2 5 3, es decir, me ahorro aproximadamente 6!
El problema es que no se me ocurre cómo implementar eso...
Por favor, si alguien puede ayudarme con esto estaría tremendamente agradecido...
este es mi código de permutaciones:
/* INICIO METODO PERMUTAR */
public static void permutar(elemento x[], int N, int dimension, int constante)
{
int c;
if(N == 1)
{
if(comprobarfilas(x, dimension, constante) && comprobarcolumnas(x, dimension, constante) && comprobarbackslash(x, dimension, constante) && comprobarslash(x, dimension, constante))
{
imprimir(x, dimension*dimension, dimension);
}
}
else
{
for(c = 0 ; c < N ; c++)
{
swap(x, c, N-1);
permutar(x, N-1, dimension, constante);
swap(x, c, N-1);
}
}
}//permutar
/* FIN METODO PERMUTAR */
Si se fijan, lo que hace es que una vez que encuentra una permutación que cumple con las propiedades de los cuadrados mágicos, la imprime en pantalla (en consola)...
Lo otro imortante es que no estoy tomando el cuadrado como una "matriz" (array bidimensional), sino que como un arreglo de elementos. Estos elementos son una clase que hice, llamada elementos, donde cada elemento tiene un int valor, y un boolean marcado... (lo hice así por si me servía después para hacer las optimizaciones)..
Bueno, eso es todo, gracias por darse la lata de leer, cualquier ayuda que me puedan dar es bienvenida, ya sea aquí en el foro o por mail...
una forma de mejorar un poquito el algoritmo es haciendo un sólo swap dentro de permutar(), o sea, hacer el primero, pero no el que está después de la llamada recursiva... pero igual no es suficiente...
void intercambiar(int *p1, int *p2) {
int aux;
aux = *p1;
*p1 = *p2;
*p2 = aux;
}
void permutar(int vector[], int sub_size, int vec_size) {
int i;
if (sub_size > 1)
for (i = 0; i < sub_size; i++) {
intercambiar(&vector[i], &vector[sub_size-1]);
permutar(vector, sub_size-1, vec_size);
intercambiar(&vector[i], &vector[sub_size-1]);
}
else
escribir(vector, vec_size);
}
Foros de debate
Java (básico)
