Generador de Combinaciones de n, r en Consola en Java

Generador de Combinaciones de n, r en Java

Gracias a la pregunta de una amiga sobre Matemáticas Discretas, en esta ocasión quiero compartir un poco acerca de la combinatoria enumerativa, la cual estudia los métodos para contar (enumerar) las distintas configuraciones de los elementos de un conjunto que cumpla con ciertos criterios especificados.

Esta fue una de las primeras áreas de la combinatoria en ser desarrollada, y como otras áreas más recientes se estudian sólo en cursos especializados, es común que se haga referencia a esta subárea cuando se menciona combinatoria en entornos educativos.

Un ejemplo citado de Wikipedia para facilitar la comprensión de este artículo es el siguiente:

Considérese el conjunto S = {A, E, I, O, U}. Podemos imaginar que estos elementos corresponden a tarjetas dentro de un sombrero.

• Un primer problema podría consistir en hallar el número de formas diferentes en que podemos sacar las tarjetas una después de otra (es decir, el número de permutaciones del conjunto). Por ejemplo, dos formas distintas podrían ser: EIAOU o OUAIE.
• Después, se puede preguntar por el número de formas en que se puede sacar sólo 3 tarjetas del sombrero (es decir, el número de 3-permutaciones del conjunto). En este caso, ejemplos pueden ser IOU, AEI o EAI.
• También se puede preguntar sobre cuáles son los posibles grupos de 3 tarjetas que se pueden extraer, sin dar consideración al orden en que salen (en otras palabras, el valor de un coeficiente binomial). Aquí, consideraríamos AOU y UAO como un mismo resultado.
• Otro problema consiste en hallar el número de formas en que pueden salir 5 tarjetas, una tras otra, pero en cada momento se regresa la tarjeta escogida al sombrero. En este problema los resultados posibles podrían ser EIOUO, IAOEU o IEAEE.

Luego de esta explicación teórica procedamos a trabajar con el código, la siguiente función genera las combinaciones utilizando un algoritmo de Kenneth H. Rosen.

//La función recibe los valores de n y r como argumentos

public static void combinaciones(int n, int r)

{

        int i = 0, j = 0, ci = 0;

        int v[] = new int[n];

        for(i = 0; i < n; i++)

        { v[i]=i; }

        escribe(v, r);

        ci++;

        while(ci < p1)

        {

            i = r - 1;

            while (v[i] == n - r + i) { i--; }

                   

            v[i] = v[i] + 1;

            for (j = i + 1; j < r; j++) { v[j] = v[i] + j - i; }

            escribe(v,r);

            ci++;

        }

}

La función de nombre "escribe" que es llamada en el código anterior nos sirve para imprimir los resultados en la consola del IDE, para descargar una copia completa del Programa funcionando procede a la JavaBox al final del Blog.