Generar combinaciones en Java

1. Introducción

En este tutorial, discutiremos la solución del problema de k combinaciones en Java .

Primero, discutiremos e implementaremos algoritmos tanto recursivos como iterativos para generar todas las combinaciones de un tamaño dado. Luego, revisaremos las soluciones que utilizan bibliotecas Java comunes.

2. Resumen de combinaciones

En pocas palabras, una combinación es un subconjunto de elementos de un conjunto dado .

A diferencia de las permutaciones, el orden en el que elegimos los elementos individuales no importa. En cambio, solo nos importa si un elemento en particular está en la selección.

Por ejemplo, en un juego de cartas, tenemos que repartir 5 cartas de un paquete que consta de 52 cartas. No nos interesa el orden en que se seleccionaron las 5 cartas. Más bien, solo nos importa qué cartas están presentes en la mano.

Algunos problemas requieren que evaluemos todas las combinaciones posibles. Para hacer esto, enumeramos las diversas combinaciones.

El número de formas distintas de elegir elementos "r" del conjunto de elementos "n" se puede expresar matemáticamente con la siguiente fórmula:

Por tanto, la cantidad de formas de elegir elementos puede crecer exponencialmente en el peor de los casos. Por lo tanto, para poblaciones grandes, puede que no sea posible enumerar las diferentes selecciones.

En tales casos, podemos seleccionar al azar algunas selecciones representativas. El proceso se llama muestreo .

A continuación, revisaremos los distintos algoritmos para enumerar combinaciones.

3. Algoritmos recursivos para generar combinaciones

Los algoritmos recursivos suelen funcionar dividiendo un problema en problemas más pequeños similares. Este proceso continúa hasta que llegamos a la condición de terminación, que también es el caso base. Luego resolvemos el caso base directamente.

Discutiremos dos formas de subdividir la tarea de elegir elementos de un conjunto. El primer enfoque divide el problema en términos de los elementos del conjunto. El segundo enfoque divide el problema siguiendo solo los elementos seleccionados.

3.1. Partición por elementos en todo el conjunto

Dividamos la tarea de seleccionar elementos " r" de " n" elementos inspeccionando los elementos uno por uno. Para cada elemento del conjunto, podemos incluirlo en la selección o excluirlo.

Si incluimos el primer elemento, entonces tenemos que elegir la opción “r - 1" elementos de los restantes “ n - 1" elementos . Por otro lado, si descartamos el primer elemento, entonces tenemos que seleccionar " r" elementos de los restantes " n - 1" elementos.

Esto se puede expresar matemáticamente como:

Ahora, veamos la implementación recursiva de este enfoque:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else if (start <= end) { data[index] = start; helper(combinations, data, start + 1, end, index + 1); helper(combinations, data, start + 1, end, index); } }

El método auxiliar realiza dos llamadas recursivas a sí mismo. La primera llamada incluye el elemento actual. La segunda llamada descarta el elemento actual.

A continuación, escribamos el generador de combinación usando este método auxiliar :

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n-1, 0); return combinations; }

En el código anterior, el método generate configura la primera llamada al método auxiliar y pasa los parámetros apropiados.

A continuación, llamemos a este método para generar combinaciones:

List combinations = generate(N, R); for (int[] combination : combinations) { System.out.println(Arrays.toString(combination)); } System.out.printf("generated %d combinations of %d items from %d ", combinations.size(), R, N);

Al ejecutar el programa, obtenemos el siguiente resultado:

[0, 1] [0, 2] [0, 3] [0, 4] [1, 2] [1, 3] [1, 4] [2, 3] [2, 4] [3, 4] generated 10 combinations of 2 items from 5

Finalmente, escribamos el caso de prueba:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSetRecursiveAlgorithm_thenExpectedCount() { SetRecursiveCombinationGenerator generator = new SetRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Es fácil observar que el tamaño de pila requerido es el número de elementos del conjunto. Cuando la cantidad de elementos en el conjunto es grande, digamos, mayor que la profundidad máxima de la pila de llamadas, desbordaremos la pila y obtendremos un StackOverflowError .

Por lo tanto, este enfoque no funciona si el conjunto de entrada es grande.

3.2. Partición por elementos en la combinación

En lugar de rastrear los elementos en el conjunto de entrada, dividiremos la tarea rastreando los elementos en la selección .

Primero, ordenemos los elementos del conjunto de entrada utilizando los índices "1" a " n" . Ahora, podemos elegir el primer elemento de los primeros elementos " n-r + 1" .

Supongamos que elegimos el k-ésimo elemento. Luego, tenemos que elegir " r - 1" elementos de los " n - k" elementos restantes indexados " k + 1" a " n" .

Expresamos este proceso matemáticamente como:

A continuación, escribamos el método recursivo para implementar este enfoque:

private void helper(List combinations, int data[], int start, int end, int index) { if (index == data.length) { int[] combination = data.clone(); combinations.add(combination); } else { int max = Math.min(end, end + 1 - data.length + index); for (int i = start; i <= max; i++) { data[index] = i; helper(combinations, data, i + 1, end, index + 1); } } }

En el código anterior, el bucle for elige el siguiente elemento, luego llama al método helper () de forma recursiva para elegir los elementos restantes . Nos detenemos cuando se ha seleccionado el número requerido de elementos.

A continuación, usemos el método auxiliar para generar selecciones:

public List generate(int n, int r) { List combinations = new ArrayList(); helper(combinations, new int[r], 0, n - 1, 0); return combinations; }

Finalmente, escribamos un caso de prueba:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingSelectionRecursiveAlgorithm_thenExpectedCount() { SelectionRecursiveCombinationGenerator generator = new SelectionRecursiveCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

El tamaño de la pila de llamadas utilizado por este enfoque es el mismo que el número de elementos de la selección. Por lo tanto, este enfoque puede funcionar para entradas grandes siempre que el número de elementos a seleccionar sea menor que la profundidad máxima de la pila de llamadas.

Si el número de elementos a elegir también es grande, este método no funcionará.

4. Algoritmo iterativo

En el enfoque iterativo, comenzamos con una combinación inicial. Luego, seguimos generando la siguiente combinación a partir de la actual hasta que hayamos generado todas las combinaciones .

Generemos las combinaciones en orden lexicográfico. Comenzamos con la combinación lexicográfica más baja.

Para obtener la siguiente combinación de la actual, encontramos la ubicación más a la derecha en la combinación actual que se puede incrementar. Luego, incrementamos la ubicación y generamos la combinación lexicográfica más baja posible a la derecha de esa ubicación.

Escribamos el código que sigue este enfoque:

public List generate(int n, int r) { List combinations = new ArrayList(); int[] combination = new int[r]; // initialize with lowest lexicographic combination for (int i = 0; i < r; i++) { combination[i] = i; } while (combination[r - 1] < n) { combinations.add(combination.clone()); // generate next combination in lexicographic order int t = r - 1; while (t != 0 && combination[t] == n - r + t) { t--; } combination[t]++; for (int i = t + 1; i < r; i++) { combination[i] = combination[i - 1] + 1; } } return combinations; }

A continuación, escribamos el caso de prueba:

@Test public void givenSetAndSelectionSize_whenCalculatedUsingIterativeAlgorithm_thenExpectedCount() { IterativeCombinationGenerator generator = new IterativeCombinationGenerator(); List selection = generator.generate(N, R); assertEquals(nCr, selection.size()); }

Ahora, usemos algunas bibliotecas de Java para resolver el problema.

5. Bibliotecas Java que implementan combinaciones

En la medida de lo posible, deberíamos reutilizar las implementaciones de bibliotecas existentes en lugar de implementar las nuestras. En esta sección, exploraremos las siguientes bibliotecas de Java que implementan combinaciones:

  • Apache Commons
  • Guayaba
  • CombinatoricsLib

5.1. Apache Commons

The CombinatoricsUtils class from Apache Commons provides many combination utility functions. In particular, the combinationsIterator method returns an iterator that will generate combinations in lexicographic order.

First, let's add the Maven dependency commons-math3 to the project:

 org.apache.commons commons-math3 3.6.1 

Next, let's use the combinationsIterator method to print the combinations:

public static void generate(int n, int r) { Iterator iterator = CombinatoricsUtils.combinationsIterator(n, r); while (iterator.hasNext()) { final int[] combination = iterator.next(); System.out.println(Arrays.toString(combination)); } }

5.2. Google Guava

The Sets class from Guava library provides utility methods for set-related operations. The combinations method returns all subsets of a given size.

First, let's add the maven dependency for the Guava library to the project:

 com.google.guava guava 27.0.1-jre 

Next, let's use the combinations method to generate combinations:

Set
    
      combinations = Sets.combinations(ImmutableSet.of(0, 1, 2, 3, 4, 5), 3);
    

Here, we are using the ImmutableSet.of method to create a set from the given numbers.

5.3. CombinatoricsLib

CombinatoricsLib is a small and simple Java library for permutations, combinations, subsets, integer partitions, and cartesian product.

To use it in the project, let's add the combinatoricslib3 Maven dependency:

 com.github.dpaukov combinatoricslib3 3.3.0 

Next, let's use the library to print the combinations:

Generator.combination(0, 1, 2, 3, 4, 5) .simple(3) .stream() .forEach(System.out::println);

This produces the following output on execution:

[0, 1, 2] [0, 1, 3] [0, 1, 4] [0, 1, 5] [0, 2, 3] [0, 2, 4] [0, 2, 5] [0, 3, 4] [0, 3, 5] [0, 4, 5] [1, 2, 3] [1, 2, 4] [1, 2, 5] [1, 3, 4] [1, 3, 5] [1, 4, 5] [2, 3, 4] [2, 3, 5] [2, 4, 5] [3, 4, 5]

More examples are available at combinatoricslib3-example.

6. Conclusion

In this article, we implemented a few algorithms to generate combinations.

También revisamos algunas implementaciones de bibliotecas. Por lo general, las usamos en lugar de las nuestras.

Como de costumbre, el código fuente completo se puede encontrar en GitHub.