Número Combinatorio en Java

Más ejercicios resueltos

Si deseas revisar más ejercicios resueltos, haz click en el siguiente botón. 

El cálculo del número combinatorio o también conocido como los coeficientes binomiales, es un problema interesante para resolver en el mundo de la programación. Esto pues, permite ver diversas técnicas para su implementación que incluyen la Fuerza Bruta, la Recursión y la Programación Dinámica. Además, aplicando simples conocimientos matemáticos, es posible optimizar el algoritmo. En este artículo, analizamos al detalle y paso a paso, el algoritmo para el cálculo del número combinatorio en Java presentando 4 distintas alternativas de solución. Si deseas conocer con más detalle la definición del número combinatorio usada en este problema, haz click en el siguiente enlace.

A continuación presentamos las 4 alternativas de solución que nos permitirán entender cómo se calculan los números combinatorios en Java. Se analizará cada alternativa con suficiente detalle como para entender la lógica de programación que subyace a cada algoritmo. Las versiones que se analizarán son las siguientes:

  • Versión usando la técnica de Fuerza Bruta
  • Versión usando la técnica de Fuerza Bruta optimizada
  • Versión usando la recursión
  • Versión usando la técnica de Programación Dinámica

Método principal

Realizaremos primero la implementación del método \texttt{main}. Este será el mismo para las primeras 3 versiones. Tiene básicamente 3 objetivos:

  • Leer los datos de entrada.
  • Validar los datos leídos.
  • Invocar a la función que se encargará de realizar el cálculo del número combinatorio.
 
La lectura de datos la realizaremos con la clase \texttt{Scanner}. Instanciamos un objeto de esta clase, que en este programa hemos denominado \texttt{reader} y procedemos con la lectura. Usaremos las variables \texttt{n} y \texttt{k} respectivamente, las cuales han sido declaradas con el tipo \texttt{int}. A cada una de estas variables, le asignamos el valor que se obtiene al ejecutar el método \texttt{nextInt} de la clase \texttt{Scanner}. Recuerde que para usar la clase \texttt{Scanner} debe importarse esta desde \texttt{java.util.Scanner}.
 
La validación la realizaremos con una selectiva doble anidada. En Java, las condicionales dobles se implementan con la estructura de control \texttt{if..else}. En la primera validación verificamos que tanto \texttt{n} como \texttt{k} sean mayores o iguales que cero. En caso no se cumpla una de estas condiciones, se emitirá el mensage \texttt{n y k deben ser mayores o iguales que cero}. En la segunda validación, en la anidación, verificamos que \texttt{k} \leq \texttt{n}, por lo que se emitirá el mensaje \texttt{n debe ser mayor o igual que k} en caso la condición no se cumpla. 
 
Una vez que los datos de entrada se han validado, se procede a invocar a la función \texttt{combinatorio} usando como argumento los valores leídos y almacenados en las variables \texttt{n} y \texttt{k}. La invocación se realiza al momento de hacer la impresión. 
package numero_combinatorio_v1;

import java.util.Scanner;

public class Numero_Combinatorio_v1 {

    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        System.out.printf("Ingrese n: ");
        int n = reader.nextInt();
        System.out.printf("Ingrese k: ");
        int k = reader.nextInt();

        if (n < 0 || k < 0) {
            System.out.printf("n y k deben ser mayores o iguales  que cero%n");
        } else if (k > n) {
            System.out.printf("n debe ser mayor o igual que k%n");
        } else {
            System.out.printf("El combinatorio de n en k es %d%n", combinatorio(n, k));
        }
    }
} 

Método combinatorio: versión usando Fuerza Bruta

A continuación presentamos la primera versión del cálculo del combinatorio en Java. Se basa en la técnica de la Fuerza Bruta. Recuerde que la fuerza bruta es un enfoque directo para resolver un problema, generalmente directamente basado en el enunciado del problema y las definiciones de los conceptos involucrado. Es justamente esto último lo que usaremos para resolver esta alternativa de solución.

Para esto nos basamos directamente en la definición matemática del número combinatorio:

\displaystyle C_k^n= \binom{n}{k}=\frac{n!}{k! \times (n-k)!}

 

Nos basamos también en el método \texttt{factorial} que se describe en la siguiente sección. El método \texttt{factorial} se encargará de retornarnos el valor del factorial de un determinado número. El método \texttt{combinatorio} básicamente realiza 3 invocaciones para calcular los factoriales necesarios (n!, k! y (n-k)!) para retornar el valor requerido. Es la alternativa más simple de implementar, pero como veremos posteriormente, no es la forma más eficiente.

    public static long combinatorio(int n, int k) {
        return factorial(n) / (factorial(n - k) * factorial(k));
    } 

A continuación, presentamos la versión del método \texttt{factorial} usada en esta alternativa de solución. La hemos diseñado usando la instrucción \texttt{for}, pero existen muchas formas de implementar este método. En nuestro artículo, Factorial en Java encontrarás 5 distintas alternativas de solución a la implementación del cálculo del número factorial.

    public static long factorial(int n) {
        long productoria = 1;
        for (int i = 2; i <= n; i++) {
            productoria *= i;
        }
        return productoria;
    } 

Método combinatorio: versión usando Fuerza Bruta optimizada

A continuación presentamos nuestra segunda alternativa de solución a los coeficientes binomiales en PSeInt. Se basa también en la técnica de la Fuerza Bruta pero optimizando las instrucciones para no ejecutar tantas iteraciones. Para esta optimización visitamos nuevamente la definición matemática de los combinatorios:

\displaystyle C_k^n= \binom{n}{k}=\frac{n!}{k! \times (n-k)!}

Pero expandimos su definición considerando la definición del factorial. La fórmula del combinatorio se puede expresar de la siguiente manera:

\displaystyle C_k^n=\frac{n \times n-1 \times n-2 \times \cdots \times 3 \times 2 \times 1}{(k \times k-1 \times k-2 \times \cdots \times 3 \times 2 \times 1) \times (n-k \times n-k-1 \times n-k-2 \times \cdots \times 3 \times 2 \times 1)}

¿Qué se puede observar? A simple vista no se pude observar ningún patrón pero veamos un par de ejemplos para que nos aclare el panorama. Veamos qué operaciones se deben ejecutar para calcular el combinatorio de 10 en 3.

\displaystyle C_3^{10}=\frac{10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1) \times (7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 )}

Como se puede apreciar, la fracción que se obtiene se puede simplificar eliminando el factorial de n-k, que en este caso es 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1, tanto del numerador como del denominador. El resultado de la simplificación es:

\displaystyle C_3^{10}=\frac{10 \times 9 \times 8}{3 \times 2 \times 1}

Con esta simplificación se tienen menos términos en la productoria final por lo que el computador realizará menos iteraciones. Veamos ahora otro ejemplo, el combinatorio de 11 en 8.

\displaystyle C_8^{11}=\frac{11 \times 10 \times 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1) \times (3 \times 2 \times 1 )}

En este caso, este cálculo se puede simplificar eliminando tanto del númerador y del denominador, el factorial de k que en este ejemplo es 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1. Simplificando se obtiene:

\displaystyle C_8^{11}=\frac{11 \times 10 \times 9}{3 \times 2 \times 1}

Usaremos esta simplificación para reducir las operaciones que se ejecutan en la versión anterior. Pero, ¿cómo realizar la simplificación?, dependiendo de los valores de n y k, se puede simplificar el factorial de k o el factorial de n-k¿Cuál de los dos valores seleccionamos? Pues como deseamos minimizar las operaciones de cálculo, entonces escogemos para la simplificación, el mayor valor de ambos.

Al optar desarrollar el problema del cálculo del combinatorio de esta forma, ya no tenemos un problema en donde el cálculo se basa en el desarrollo del factorial, sino otro problema de productoria. El problema se reduce a calcular las productorias del numerador y el denominador.

Para este cálculo es necesario saber quién es el mayor y menor entre k y n-k. Los elementos de la productoria del numerador van desde el sucesor de mayor hasta n. Los elementos de la productoria del denominador van desde 1 hasta el número menor. El algoritmo planteado para optimizar la versión del cálculo del número binomial usando fuerza bruta se basa en los siguientes puntos:

  • Calcular el mayor y menor número entre k y n-k.
  • Calcular la productoria del numerador iterando en el rango [mayor+1..n].
  • Calcular la productoria del denominador iterando en el rango [1..menor].
  • Calcular el combinatorio usando el numerador y denominador antes calculados.
    public static long combinatorio(int n, int k) {
        int n_menos_k = n - k;
        int numero_mayor, numero_menor;
        if (k > n_menos_k) {
            numero_mayor = k;
            numero_menor = n_menos_k;
        } else {
            numero_mayor = n_menos_k;
            numero_menor = k;
        }
        long numerador = 1;        
        for (int i = numero_mayor + 1; i <= n; i++) {
            numerador *= i;
        }
        long denominador = 1;
        for (int i = 1; i <= numero_menor; i++) {
            denominador *= i;
        }
        return numerador / denominador;
    } 

Método combinatorio: versión Recursiva

A continuación presentamos nuestra tercera alternativa de solución a los números combinatorios en PSeInt. Para esta versión, usaremos la Recursión. Para esto nos basamos en la definición recursiva. Según la definición dada, el caso recursivo es:

\displaystyle \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

Y los casos directos son:

\displaystyle \binom{n}{0}=1 para n \geq 0

\displaystyle \binom{0}{k}=0 para k > 0

Pero, ¿cómo funciona la recursión? Pues se invoca a la misma función de manera recurrente hasta llegar a un caso directo. Por ejemplo veamos como se ejecuta el combinatorio de 3 en 2.

\displaystyle \binom{3}{2}=\binom{2}{1}+\binom{2}{2}

Pero esto conlleva a invocar nuevamente al combinatorio. Se tienen dos operaciones a realizar, el combinatorio de 2 en 1 y el combinatorio de 2 en 2

\displaystyle \binom{2}{1}=\binom{1}{0}+\binom{1}{1}

\displaystyle \binom{2}{2}=\binom{1}{1}+\binom{1}{2}

Analizaremos primero el combinatorio de 2 en 1
 
\displaystyle \binom{2}{1}=\binom{1}{0}+\binom{1}{1}
 
En este caso, se llega al combinatorio de 1 en 0, el cual es uno de los casos directos, este combinatorio equivale a 1 según la definición dada. Pero hay que realizar la invocación recursiva para el caso del combinatorio de 1 en 1. De esta forma el combinatorio de 2 en 1 quedaría como:
 
\displaystyle \binom{2}{1}=1 + \binom{0}{0}+\binom{0}{1}
 
En este caso, tanto el combinatorio de 0 en 0 como el combinatorio de 0 en 1 son casos directos. El primero vale 1 y el segundo 0. De esta forma, el combinatorio de 2 en 1 sería:
 
\displaystyle \binom{2}{1}=1 + 1+0=2
 
Analizaremos, en segundo lugar, el combinatorio de 2 en 2
 
\displaystyle \binom{2}{2}=\binom{1}{1}+\binom{1}{2}
 
Nuevamente tenemos dos casos para analizar, el combinatorio de 1 en 1 y el combinatorio de 1 en 2.
 
El combinatorio de 1 en 1 ya ha sido analizado anteriormente y corresponde con:
 
\displaystyle \binom{1}{1}=\binom{0}{0}+\binom{0}{1}=1+0=1
 
Para el caso del combinatorio de 1 en 2 nuevamente se hace una invocación recursiva de la siguiente manera: 
 
\displaystyle \binom{1}{2}=\binom{0}{1}+\binom{0}{2}
 
Tanto el combinatorio de 0 en 1 como el combinatorio de 0 en 2 son casos directos y ambos valen 0, por lo tanto:
 
\displaystyle \binom{1}{2}=0+0=0
 
Por lo tanto, el combinatorio de 2 en 2 equivale a:
 
\displaystyle \binom{2}{2}=\binom{1}{1}+\binom{1}{2}=1+0=1
 
Una vez que se han calculados los números combinatorios requeridos por recurrencia, podemos calcular el combinatorio de 3 en 2. La operación quedaría de la siguiente manera:

\displaystyle \binom{3}{2}=\binom{2}{1}+\binom{2}{2} = 2+1=3

Para la implementación recursiva de los números binomiales en Java, los casos directos los hemos implementamos a través de una selectiva simple de forma tal que se invoque a la recursión si es que no se satisface ningún caso directo. Recuerde que si se ejecuta la instrucción \texttt{return} dentro de una función, la función termina por lo que no se ejecutará ninguna instrucción posterior. Es por este motivo que no se ha usado la claúsula \texttt{else} en este caso.

    public static long combinatorio(int n, int k) {
        if (n >= 0 && k == 0) {
            return 1;
        }
        if (n == 0 && k > 0) {
            return 0;
        }
        return combinatorio(n - 1, k - 1) + combinatorio(n - 1, k);
    } 

Versión usando Programación Dinámica

Como podrá notar, de todas las versiones anteriores, la versión recursiva es la más simple de implementar pero no es la más eficiente. Pero, ¿por qué afirmamos que en este caso la recursión no es la forma de implementación más eficiente? Sucede que en las llamadas recursivas, como estas se ejecutan de forma independiente, muchas de ellas se repiten más de una vez. Por ejemplo, para el caso analizado en la sección anterior, para el combinatorio de 3 en 2, se calcula el combinatorio de 1 en 1 dos veces. Para valores de n y k mayores, la cantidad de repeticiones aumenta.

Para evitar estas repeticiones usaremos la Programación Dinámica. Esta técnica busca reducir el tiempo de ejecución de un algoritmo usando soluciones previas ya conocidas. Para esto se almacenan las soluciones ya conocidas en una estructura, típicamente arreglos y se suelen reutilizar las veces que sean necesarias. El problema en esta técnica se reduce a inicializar este arreglo.

Método principal

Vamos a diseñar el método principal para el cálculo de los combinatorios en Java. Tiene básicamente 4 objetivos:

  • Leer los datos de entrada.
  • Validar los datos leídos.
  • Invocar al método que se encargará de realizar la inicialización del arreglo.
  • Retornar el valor del combinatorio usando el arreglo antes inicializado.
 
La principal diferencia que vemos en relación a las versiones anteriores, es que en esta versión no existe un método llamado \texttt{combinatorio}, en su lugar existe un arreglo. Para hallar el valor del combinatorio deseado, se buscará el mismo en dicho arreglo. Dado que los números combinatorios se definen con dos valores, el arreglo será bidimensional, en donde la primera dimensión representa al número n y la segunda dimensión al número k. De esta forma si se quisiera el combinatorio de 3 en 2, no se invocaría al método \texttt{combinatorio(3,2)}  sino se buscaría dicho valor en el arreglo de la siguiente manera: \texttt{combinatorio[3,2]}.      
 
La ventaja que ofrece esta técnica es que el arreglo se inicializa una única vez y puede ser usado las veces que sea necesario. Evitando la realización de cálculos innecesarios. Es aquí donde radica su potencia.

El arreglo ha sido declarado con la instrucción \texttt{long combinatorio[][]}. Y se ha instanciado con la instrucción \texttt{new long [DIMENSION][DIMENSION]}. Como la constante \texttt{DIMENSION} se ha inicializado con 20, significa que el arreglo tendrá 20 elementos en la dimensión 1 y 20 elementos en la dimensión 2. Como los índices en Java inician en 0, los índices válidos para el arreglo serán [0..19][0..19]. Se ha escogido el tamaño de la dimensión de forma arbitraria pero esta deberá estar de acorde a los datos que se esperan en un problema en particular.
package numero_combinatorio_v4;

import java.util.Scanner;

public class Numero_Combinatorio_v4 {

    private static final int DIMENSION = 20;
    private static long combinatorio[][];

    public static void main(String[] args) {
        Scanner reader = new Scanner(System.in);
        System.out.printf("Ingrese n: ");
        int n = reader.nextInt();
        System.out.printf("Ingrese k: ");
        int k = reader.nextInt();

        if (n < 0 || k < 0) {
            System.out.printf("n y k deben ser mayores o iguales que cero%n");
        } else if (k > n) {
            System.out.printf("n debe ser mayor o igual que k%n");
        } else {
            combinatorio = new long[DIMENSION][DIMENSION];
            inicializar_arreglo();
            System.out.printf("El combinatorio de n en k es %d%n", combinatorio[n][k]);
        }
    }
} 

Inicialización del arreglo

Como habíamos comentado anteriormente, requerimos poblar el arreglo en donde estarán los números combinatorios. Este será un arreglo de dos dimensiones, una para el valor de n y otra para el valor de k. El número de la fila representará al valor de n y el número de la columna representará al valor de k. Recuerde que hemos configurado PSeInt para que inicie el conteo de los índices en 0.

Usamos una propiedad de los combinatorios que dice que «cualquier combinatorio sobre 0 es igual a 1». Esto significa que la columna 0 siempre tendrá el valor de uno. Nunca cambiará. Es un valor para inicializar la columna 0.

n\k

0

1

2

3

4

5

0

1






1

1

2

1

3

1

4

1

5

1

Ahora nos aprovecharemos una segunda propiedad de los números binomiales «Todo combinatorio sobre sí mismo es igual a 1». Esto significa que cuando n=k, el combinatorio será 1. Cuando se cumple la condición n=k, nos encontraremos en la diagnonal izquierda, por lo que la matríz quedaría así:

n\k

0

1

2

3

4

5

0

1






1

1

1

2

1

1

3

1

1

4

1

1

5

1

1

¿Cómo hacemos para llenas los combinatorios faltante? pues hacemos usado de la definición recursiva que dice:

\displaystyle \binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}

En términos prácticos, cada celda vacía de la diagonal inferir es igual a la suma de la celda de la diagonal superior izquierda, más la celda superior. 

En el caso del \texttt{combinatorio[2,1]} \texttt{=} \texttt{combinatorio[1,0]} \texttt{+} \texttt{combinatorio[1,1]}.

n\k

0

1

2

3

4

5

0

1






1

1

1

2

1

2

1

3

1

3

3

1

4

1

4

6

4

1

5

1

5

10

10

5

1

    public static void inicializar_arreglo() {
        for (int i = 0; i < DIMENSION; i++) {
            combinatorio[0][i] = 0;
            combinatorio[i][0] = 1;
        }
        for (int n = 1; n < DIMENSION; n++) {
            for (int k = 1; k <= n; k++) {
                combinatorio[n][k] = combinatorio[n - 1][k - 1] + combinatorio[n - 1][k];
            }
        }
    } 

Conclusión

Hemos presentado en este artículo, 4 alternativas de solución al cálculo de los combinatorios usando Java. Se han utilizado estructuras iterativas, la técnica de la fuerza bruta, la recursión y la programación dinámica.  Podrá descargar la solución propuesta en el repositorio GitHub de iterando++ a través del siguiente enlace

Hemos preparado otros artículos adicionales en donde describimos al detalle la implementación de este problema en lenguajes de programación. Te invitamos a leer los siguientes artículos de iterando++

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *