viernes, 25 de febrero de 2011

Combinaciones sin repetición en Java (I)

Para un trabajo de una asignatura he necesitado calcular las combinaciones sin repetición de un cierto tamaño de una lista. Al final he obtenido dos métodos, uno recursivo (con ayuda de Edulix) y otro iterativo (con ayuda de Daniel Cáceres) hecho con los iteradores:

RECURSIVO

public static void comb(List<String> a, List<String> b,List<List<String>> solutions, int depth) {

  if (a.size() == depth) {
           Collections.sort(a);
               if (!solutions.contains(a)) {
                 solutions.add(a);
                }

   }

for (String str : b) {
 List<String> aux = new LinkedList<String>();
 List<String> baux = new LinkedList<String>();
 baux.addAll(b);
 baux.remove(str);
 aux.addAll(a);
 aux.add(str);
 comb(aux, baux, solutions, depth);

 if (!solutions.isEmpty()) {
  break;
 }

  }
}



Siendo la lista a una lista de strings vacía, la lista de strings b la lista con los elementos a hacer las combinaciones y sol una lista de listas de strings en dónde estarán las soluciones. El int depth es el tamaño de los conjuntos de las combinaciones.

La versión iterativa la dejaremos para otro post pero os puedo ir adelantando que es casi 4 veces más rápida que esta versión =)

Si tienen alguna duda sobre este artículo o algún otro tema en el que pueda ser útil, no dude en mandarme un mail a: bobsfera@gmail.com o escribe un comentario!

No hay comentarios:

Publicar un comentario en la entrada