jueves, octubre 14, 2010

Generar combinaciones de caracteres

Generación con sustitución

Si se quieren generar todas las posibles cadenas que se forman con un determinado número de caracteres, una primera estrategia es hacer un programa con ciclos anidados, uno para cada posición de la cadena que se debe generar. Un ejemplo de esta estrategia es el siguiente:


// Generar secuencias de 4 caracteres
public static void generar4Caracteres(char[] elementos) {
        String r;
        for (int i = 0; i < elementos.length; i++) {
            for (int j = 0; j < elementos.length; j++) {
                for (int k = 0; k < elementos.length; k++) {
                    for (int l = 0; l < elementos.length; l++) {
                        r=""+elementos[i]+elementos[j]+elementos[k]+elementos[l];
                        // Acá se debe hacer algo con la cadena generada
                        System.out.println(r);
                    }
                }
            }
        }
    }


La principal limitación del anterior método es que solo se generan cadenas de 4 caracteres, y en caso de requerir cadenas generadas de otro tamaño, se requiere un nuevo método, pues la cantidad de caracteres de la cadena generada es la que determina el número de ciclos for del proceso. Una mejor estrategia para generar una cadena de N caracteres es, comenzando con la cadena vacía, agregar un caracter y llamar recursivamente el mismo método para generar las cadenas de tamaño N-1. Cuando la cadena a generar sea de tamaño 0, es porque ya se completó la generación de una ocurrencia y se puede proceder a procesar la cadena generada. En este caso el método queda así:


// Permutaciones con sustitución
    public static void generarPermutacionSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i++) {
                generarPermutacionSust(elementos, actual elementos[i],cantidad-1);
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres con sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 11, 12, 13, 21, 22, 23, 31, 32 y 33


Generación sin sustitución

Cuando se requieren generar todas las posibles cadenas de determinado tamaño formadas a partir de un conjunto de caracteres pero sin que se repita ningún caracter entonces se debe llevar un pequeño control de que caracteres ya han salido para evitar su inclusión.

En este programa basado en la entrada anterior anterior del blog se agrega un arreglo de valores booleanos de 100 posiciones, aunque podría ser de mayor tamaño, en el cual cada vez que se utiliza un caracter, se marca su posición para no volverlo a usar, pero se deja disponible una vez se ha liberado el caracter de su uso:

// Permutaciones sin sustitución
    static boolean[] control = new boolean[100];
    public static void generarPermutacionNoSust(char[] elementos, String actual, int cantidad) {
        if(cantidad==0) {
            // Hacer con la secuencia generada
            System.out.println(actual);
        }
        else {
            for(int i=0; i<elementos.length; i  ) {
                if(control[i]==true) continue;
                control[i]=true;
                generarPermutacionNoSust(elementos, actual elementos[i],cantidad-1);
                control[i]=false;
            }
        }
    }


Para probar este método para generar todas las posibles subcadenas de dos caracteres sin sustitución formadas con los dígitos 1, 2 y 3, se puede utilizar este segmento de instrucciones:


String alfabeto = "123";
char[] elementos = alfabeto.toCharArray();
generarPermutacionNoSust(elementos, "", 2);


Con este código se generarían como salida las siguientes cadenas: 12, 13, 21, 23, 31 y 32

33 comentarios:

  1. Una duda, cuando declaras el metodo public static void generarPermutacionSust(char[] elementos, String actual, int cantidad) {
    actual lo declaras del tipo String, pero en la parte recursiva lo pones como generarPermutacionSust(elementos, actual elementos[i],cantidad-1);, podrias explicarme por que lo usar asi, por q la segunda vez actual elementos[i] es char y habria incopatibilidad, ademas q poner actual elementos... no entiendo, podrias explicarme por favor.

    ResponderBorrar
  2. funciona o es uno de muchos codigos que no sirven para nada

    ResponderBorrar
  3. funciona o es uno de muchos codigos que no sirven para nada

    ResponderBorrar
  4. funciona, pero no se ve:
    for(int i=0; i<elementos.length; i ) {
    hay que poner el ++ así:
    for(int i=0; i<elementos.length; i++) {

    y en:
    generarPermutacionNoSust(elementos, actual elementos[i],cantidad-1);

    hay que concatenar la letra que va encontrando así
    generarPermutacionNoSust(elementos, actual+elementos[i],cantidad-1);

    debe fallar algo en el blog y no se ven los ++.

    Lo que si he detectado es que a partir de 7 letras, aún siendo el total de permutaciones correcto, repite palabras. estoy viendo por qué

    ResponderBorrar
  5. Anónimo3:54 p.m.

    Ya encontraste por que no se ve?

    ResponderBorrar
  6. Anónimo6:46 a.m.

    Hi there i am kavin, its my first occasion to commenting anyplace,
    when i read this paragraph i thought i could also make comment due
    to this sensible paragraph.

    my site raspberry ketones diet

    ResponderBorrar
  7. Anónimo7:51 p.m.

    Me ha encantado la sencillez con que has implementado el método para calcular las combinaciones sin repeticiones.
    Por cierto ¿no te falta "++" para completar "i++" dentro del for?. A lo mejor en java se puede pero que yo sepa en C++ no.

    ResponderBorrar
  8. Anónimo12:52 a.m.

    At first that does not sound extremely special, does it?

    You require to be in a position see your folders so they appear
    like little Manilla folders. I know utilizing the telephone when driving is not recommended, but who doesn't?


    My web-site; kik for pc

    ResponderBorrar
  9. Anónimo2:16 a.m.

    When I initially commented I clicked the "Notify me when new comments are added" checkbox and now eaach time a comment is
    addced I get four e-mails with the same comment. Is there any
    way you can remove people frim that service?
    Cheers!

    Also visit my website :: Venus Factor Review (reddit.com)

    ResponderBorrar
  10. Anónimo8:04 p.m.

    Right here is the perfect webpage for anybody who would like to understand
    this topic. You know so much its almost hard to
    argue with yoou (not that I personally will need to…HaHa).
    You definitely put a brand new spin on a topic which has been discussed for many
    years. Wonderful stuff, just excellent!

    Also visit my blog post - trials frontier hack download (trialsfrontierhack.com)

    ResponderBorrar
  11. Anónimo1:52 a.m.

    Great info. Lucky me I ran across your blog by accident (stumbleupon).
    I've book-marked it for later!

    Also visit my website: iron force hack download

    ResponderBorrar
  12. Anónimo3:48 p.m.

    Quality articles is the crucial to interest the users to pay a visit the website, that's what
    this site is providing.

    ResponderBorrar
  13. Anónimo8:03 p.m.

    Hey superb blog! Does running a blog similar to this require a large amount of work?
    I have very little understanding of computer programming however I was
    hoping to start my own blog in the near future. Anyways, if you have any suggestions or techniques
    for new blog owners please share. I understand this is
    off subject but I simply wanted to ask. Many thanks!

    Stop by my page; ,lawn mower repair shop Portland Or,

    ResponderBorrar
  14. Anónimo9:07 a.m.

    Predtty nice post. ӏ jսst stumbled upon үour blog ɑnd wished tto saү that I've truly enjoyed browsing ƴouг
    blog posts. Іn ɑny caѕе I will ƅe subscribing tο yiur feed and I hope ʏou
    write agaіn soоn!

    My website; Online Guide for the best Slot machines

    ResponderBorrar
  15. Anónimo1:21 p.m.

    Building a site and getting traffic vіa soсial avenues is easy.
    However; it’s been two yrssince it’s launch, and it’s
    bеen replaced. The Google Sniper system emphasizes ߋn Αutomation and
    the way in աhich іs by creating web sites thɑt maҝe affiliate gross sales on аutoƿilot.


    Looқ into my weblоg; what men secretly Want Free

    ResponderBorrar

Multiprocesamiento recursivo en JAVA 7

Una de las estrategias de diseño de algoritmos más comunes es la de "divide y vencerás", en la cual, un problema de tamaño relativ...