viernes, 3 de mayo de 2013

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.

22 comentarios:

  1. Excelente blog =D Me ha servido de mucho sus ejemplos, continuen asi, hacen que java sea mas entendible xD

    ResponderEliminar
    Respuestas
    1. Donde se encuentra la funcion "escribe"... disculpa no entendi donde puedo obtenerla..

      Eliminar
    2. Gracias por tus palabras Mario, comentarios así hacen que sigamos adelante!! =)

      Eliminar
    3. Con respecto al método escribe que es llamado en el ejemplo, solo es una función que se creó para personalizar el formato de impresión de las combinaciones, por ejm algo así:

      public void escribe(int v[],int r)
      {
      for(int i=0;i<r;i++) {
      System.out.format("%3d",v[i]);
      }
      System.out.println("");
      }

      Espero que te sirva, saludos! =)

      Eliminar
  2. una pregunta, como lo implemento en Java

    ResponderEliminar
    Respuestas
    1. El código puesto en el post está en java, es una función, a la cual solo debes llamarla en el método Main y pasar los datos con los que deseas que este trabaje.

      Suerte!! =)

      Eliminar
    2. pero como lo implemento, desde que clase lo llamo?

      Eliminar
    3. Lo llamas desde tu clase principal, aquella que tu crees, por ejm:

      El código del post lo pones en la clase "Combinaciones.java"
      Luego creas una clase "Principal.java", la cual contiene el método Main, y desde ahí creas una instancia del objeto Combinaciones y accedes al metodo "combinaciones", pasando los datos que necesita el programa para funcionar, ahora lo único que te faltaría es implementar otro método llamado "escribe" para personalizar la forma de imprimir las combinaciones en la consola.

      Saludos!!

      Eliminar
  3. Se agradece, ahi vamos a probar como funciona

    ResponderEliminar
  4. Que es p1 ??
    no la veo inicializada, y la usas en while(ci < p1)

    ResponderEliminar
    Respuestas
    1. Hola Mario, la variable es declarada en tu clase, lo publicado es el método que te sirve para las combinaciones.

      Puedes declararla así: double p1=0;

      Igual puedes encontrar una copia de todo el código en la Java Box al final del blog.

      Suerte!!

      Eliminar
  5. Muy bueno, creo que tomaré algo para mi blog, y lo mejoraré :D Obviamente con el debido crédito ;) Espero que no sea ningún problema. Saludos.

    ResponderEliminar
    Respuestas
    1. Hola Julian, gracias por tus comentarios, claro que si, gracias por comentar y sobre lo del crédito.

      Saludos! =)

      Eliminar
  6. La variable p1 donde se declara y como se utiliza?

    ResponderEliminar
    Respuestas
    1. La variable es declarada en tu clase, lo publicado es el método que te sirve para las combinaciones.

      Puedes declararla así: double p1=0;

      Igual puedes encontrar una copia de todo el código en la Java Box al final del blog.

      Suerte!!

      Eliminar
    2. Muchas gracias me sirvió bastante

      Eliminar
    3. De nada, me alegro que te haya servido!! =)

      Eliminar
  7. Respuestas
    1. Hola, de nada, me alegra que te haya servido bastante.

      Saludos! =)

      Eliminar