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