Hack x Crack - Comunidad de Seguridad informática

Programación => Otros => Mensaje iniciado por: vichj en Febrero 10, 2020, 03:57:33 am

Título: Generador de agrupaciones
Publicado por: vichj en Febrero 10, 2020, 03:57:33 am
Estoy haciendo un programa en el que requiero generar todas las agrupaciones posibles de un conjunto de datos, con una cantidad de datos máxima por agrupación, y en la que todos los datos formen parte de un grupo.
Ejemplo: {a,b,c,d} agrupados de a 2 elementos máximo serian:

ab,cd
ac,bd
ad,bc

Es decir tres combinaciones posibles, y dos entidades por combinación.

Otro ejemplo: {a,b,c,d,e} agrupados de a 2 elementos máximo serian:

ab,cd,e     ab,ce,d     ab,de,c     ac,de,b     bc,de,a
ac,bd,e     ac,be,d     ad,be,c     ae,cd,b     bd,ce,a
ad,bc,e     ae,bc,d     ae,bd,c     ad,ce,b     be,cd,a

Es decir quince combinaciones posibles, tres entidades por combinación.

Otro ejemplo: {a,b,c,d,e} agrupados de a 3 elementos máximo serian:

abc,de
abd,ce
abe,cd
acd,be
ace,bd
ade,bc
bcd,ae
bce,ad
bde.ac
cde,ab

Es decir diez combinaciones posibles, dos entidades por combinación.

Alguien me puede orientar sobre como resolver este problema, no encuentro una solución recursiva.
Dado que la cantidad de datos es arbitraria y el numero máximo por subgrupo también es arbitrario.
Título: Re:Generador de agrupaciones
Publicado por: vichj en Febrero 20, 2020, 06:34:33 am
Ya quedo.


Código: [Seleccionar]
public class PruebaCombinacion {
   
    ArrayList<ArrayList<ArrayList<String>>> g =new ArrayList<>();
   
    ArrayList<ArrayList> m =new ArrayList<>();
   
    ArrayList<String> s = new ArrayList<>();
       
    public static void main(String[] args){
        s.add("a");
        s.add("b");
        s.add("c");
        s.add("d");
        s.add("e");
       
        generaAgrupaciones(3);
       
        System.out.println(g);
       
    }
   
    public void comb(ArrayList<String> cb, int preElemento, int left){
       
        if(left == -1 || cb.size() == s.size()){
           
            m.add(cb);
            return;
           
        }

        for(int i=preElemento; i<s.size(); i++){
           
            ArrayList<String> result = (ArrayList<String>) cb.clone();
            result.add(s.get(i));
            ArrayList<String> aux = result;
            comb(aux, i+1, left-1);
           
        }
    }
   
    public boolean isElementInComb(String el, ArrayList<String> cmb){
       
       for(int i=0; i<cmb.size(); i++){
           if(el.equals(cmb.get(i))) return true;
       }
       return false;
       
    }
   
    public boolean isColitionElementInList(ArrayList<String> cmb1, ArrayList<String> cmb2){
       
        for(int i=0; i<cmb1.size(); i++) if(isElementInComb(cmb1.get(i), cmb2)) return true;
        return false;
       
    }
   
    public void generaCombs(int elementos){

        comb(new ArrayList<String>(), 0, elementos-1);

        if(s.size() % elementos > 0 && elementos < s.size()){
            comb(new ArrayList<String>(), 0, s.size() % elementos - 1);
        }
    }
   
    public void generaAgrupaciones(int elementos){
       
        generaCombs(elementos);
       
        int agrupacionesPorGrupo;
       
        if(s.size() - elementos == 0) agrupacionesPorGrupo = 1;
        else agrupacionesPorGrupo = s.size() / elementos + 1;
       
        groups(new ArrayList<ArrayList<String>>(), 0, agrupacionesPorGrupo-1);
       
    }
   
    public void groups(ArrayList<ArrayList<String>> cb, int preElemento, int left){
       
        int suma=0;
        for(int i=0; i<cb.size(); i++){
            suma+=cb.get(i).size();
        }
       
        if(( left == -1 || cb.size() == m.size() ) && suma == s.size()){
           
            g.add(cb);
            return;
           
        }

        for(int i=preElemento; i<m.size(); i++){
           
            boolean continueI = false;
           
            for(int j=0; j<cb.size(); j++){
                if(isColitionElementInList(cb.get(j), m.get(i))) {
                    continueI = true;
                    break;
                }
            }
            if(continueI == true) continue;
           
            ArrayList<ArrayList<String>> result = (ArrayList<ArrayList<String>>) cb.clone();
            result.add(m.get(i));
            ArrayList<ArrayList<String>> aux = result;
            groups(aux, i+1, left-1);
           
        }
    }
}