Ver Mensaje Individual
  #3 (permalink)  
Antiguo 22/12/2010, 09:20
sagitario261184
 
Fecha de Ingreso: diciembre-2010
Ubicación: Lambayeque, Perú
Mensajes: 7
Antigüedad: 13 años, 11 meses
Puntos: 1
Respuesta: Problema para formar subconjuntos en java utilizando algoritmo de Backtrac

Después de pader un poco. Aquí esta la solución
package inputfile;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
/**
*
* @author Usuario
*/
public class SubconjuntosY {
List<Object[]> conjuntos;
boolean podar = false;
private HashMap<Integer,List<List<Object>>> hConjuntos = new HashMap<Integer,List<List<Object>>>();

public SubconjuntosY(List<Object[]> conjuntos) {
this.conjuntos = conjuntos;
Object[][] presente = new Object[conjuntos.size()][2];
for(int i = 0; i < conjuntos.size(); i++)
{
presente[i][0] = false;
presente[i][1] = new boolean[conjuntos.get(i).length];
}
// Inicialmente conjuntos esta todo en false
arbolPrincipal(presente, 0);
}

private void procesarSolucionPrincipal(Object[][] presente)
{
List<boolean[]> subconjuntos = new ArrayList<boolean[]>();
for (int i = 0; i < presente.length; i++)
{
if (Boolean.parseBoolean(presente[i][0].toString()))
{
//boolean[] presente1 = (boolean[])presente[i][1];
subconjuntos.add((boolean[])presente[i][1]);
}
}
if(subconjuntos.size() > 0)
this.arbolSecundario(presente, subconjuntos, 0);
}

private void arbolPrincipal(Object[][] presente,int posicionActual)
{
if(presente.length == posicionActual)
{
procesarSolucionPrincipal(presente);
//podar = true;
}
else
{
if(!podar)
{
presente[posicionActual][0] = true;
arbolPrincipal(presente, posicionActual + 1);
if(!podar)
{
presente[posicionActual][0] = false;
arbolPrincipal(presente, posicionActual + 1);
}
}
}
}

private void procesarSolucionSecundaria(Object[][] presente,List<boolean[]> subconjuntos)
{
List<Object> combinaciones = new ArrayList<Object>();
for(int i = 0; i < subconjuntos.size(); i++)
{
for(int j = 0; j < subconjuntos.get(i).length; j++)
{
if(subconjuntos.get(i)[j])
{
int k = -1;
for(int m = 0; m < presente.length; m++)
{
if(Boolean.parseBoolean(presente[m][0].toString()))
k++;
if(k == i)
{
combinaciones.add(conjuntos.get(m)[j]);
break;
}
}
break;
}
}
}
System.out.println(combinaciones);
}

private void arbolSecundario(Object[][] presente,List<boolean[]> subconjuntos,int posicionActual)
{
if(subconjuntos.size() == posicionActual)
{
procesarSolucionSecundaria(presente,subconjuntos);
}
else
{
for(int i = 0; i < subconjuntos.get(posicionActual).length; i++)
{
subconjuntos.set(posicionActual, new boolean[subconjuntos.get(posicionActual).length]);
subconjuntos.get(posicionActual)[i] = true;
arbolSecundario(presente,subconjuntos, posicionActual + 1);
}
}
}

public HashMap<Integer, List<List<Object>>> getHConjuntos() {
return hConjuntos;
}
}