Permutando cosas

¡Vuelvo con el post que todos estabais esperando! ¡Tan emocionante que no podréis parar de leer!

¡¡El código de una función recursiva que genera permutaciones de un ArrayList de cadenas de caracteres dentro de otro ArrayList en Java!!

...

Oye.

Eh, a dónde vais.

A DÓNDE VAIS.

VOLVED AQUÍ, MALDITOS.

¡Que es súper interesante! Más o menos. Un poco. BUENO VALE NO. Este post va a ser un rollo, es verdad, así que vale, podéis iros. Pero ya que me abandonáis, haced algo útil con vuestro tiempo. Aprended a cocinar. O algo de cine. O del mundo. Y si no, ahí a la derecha hay una lista de blogs estupendos.

El caso:

Estoy implementando un sistema de votaciones para mi proyecto de fin de carrera, y llegué a un punto en el que tenía que generar todas las combinaciones posibles de unos determinados elementos. Véase, si tenía

{[galleta], [tarta], [magdalena]}

yo quería obtener

{ {[galleta], [tarta], [magdalena]}

{[galleta], [magdalena], [tarta]}

{[tarta], [magdalena], [galleta]}

{[tarta], [galleta], [magdalena]}

{[magdalena], [tarta], [galleta]}

{[magdalena], [galleta], [tarta]} }

Igual os parece fácil, pero no. Más que nada porque la manera de hacerlo es empleando recursividad.

INCISO

Para los pobres incautos no ingenieros que hayáis llegado hasta aquí, os cuento que la recursividad es una técnica híper chunga de la muerte, consistente, a grandes rasgos, en que una función se llama a sí misma. Hace falta mucha práctica y mucha paciencia para manejarla bien, pero si consigues hacerte con ello, solucionas en tres líneas algoritmos muy complejos, tu fobia a las arañas y el hambre en el mundo.

FIN DEL INCISO

Por lo visto también se podían usar pilas o colas para solucionar el problema, pero de eso sí que sé cero patatero, así que me puse con la recursividad. Tras una tarde dándole vueltas al asunto vi que aquello me iba a llevar la vida implementarlo, y tengo que terminar mi proyecto para dentro de un mes, así que decidí ver si había algo ya hecho por ahí. Podéis llamarlo reutilizar, copiar, o que si no, no me da tiempo a entregar el proyecto; el caso es que no encontré exactamente lo que estaba buscando, pero sí el código de un algoritmo que permutaba caracteres. Vamos, que le pasas a la función [ABC] y te devuelve

{[ABC], [ACB], [BAC], [BCA], [CAB], [CBA]}

Este código está en ésta página, y lo ha escrito un tal Jairo Alonso al que tenemos que querer todos muchísimo, porque gracias a él he perdido dos días en adaptar código en vez de diez en fabricarlo.

Total, que el código de este hombre calcula permutaciones de caracteres, y el mío calcula permutaciones de cadenas de caracteres, y si ya he tirado dos días de mi vida adaptándolo, pues para qué lo vais a hacer vosotros también. Copiad esto y a correr.

Lo que hay que pasarle a la función es un ArrayList ArrayList String (aquí no puedo poner mayores que y menores que porque el editor se vuelve idiota) que contenga la lista de listas de cadenas que queráis permutar (ver el ejemplo de las galletas de arriba) y un int que contenga el número de resultados que tienen que calcularse. Esto será el factorial del número de elementos de la lista que le hemos pasado, que se calcula con la función getFactorial que también incluyo a continuación. Por lo que he dicho de que el editor se vuelve tonto, donde ponga ArrayList> vosotros tenéis que poner ArrayList menorque ArrayList menorque String mayorque mayorque.

public static ArrayList> permutar(ArrayList originalList,int numberOfWantedElements){
   
        ArrayList> permutedList = new ArrayList>();
        int numberOfOriginalElements = originalList.size();
        ArrayList> aux = permutacion(originalList);
   
        if(numberOfWantedElements == 1 || numberOfOriginalElements == 1){

            if(permutedList.isEmpty()){
               
                permutedList.add(originalList);
           
            } else{
               
                ArrayList> potato = new ArrayList>();
               
                potato.add(originalList);
               
                for(int f=0 ; f                   
                    potato.add(permutedList.get(f));
                }
                   
                permutedList = (ArrayList>)potato.clone();
            }
       
            return permutedList;
        }

        for(int i=0 ; i   
            ArrayList anotherAux = new ArrayList();
           
            for(int h=1 ; h               
                anotherAux.add(aux.get(i).get(h));
            }
           
            ArrayList> auxiliar = permutar(anotherAux, getFactorial(numberOfOriginalElements-1));
           
            for(int j=0 ; j               
                ArrayList carrot = new ArrayList();
               
                carrot.add(aux.get(i).get(0));
               
                for(int y=0 ; y                   
                    carrot.add(auxiliar.get(j).get(y));
                }
               
                permutedList.add(carrot);
            }           
        }

        return permutedList;
    }
   
   
    public static ArrayList> permutacion(ArrayList originalList2) {
       
        ArrayList originalList = originalList2;
        int originalListSize = originalList.size();
        ArrayList temp = new ArrayList();
        ArrayList> vector = new ArrayList>();
       
        vector.add(originalList);
   
        for(int i=1 ; i       
            for(int j=0 ; j           
                if(j == originalListSize-1){
                   
                    ArrayList temp2 = new ArrayList();

                    temp2.add(originalList.get(j));
                   
                    for(int k=0 ; k                       
                        temp2.add(temp.get(k));
                    }
                   
                    temp = temp2;
               
                } else{
                   
                    temp.add(originalList.get(j));
                }   
            }
       
            originalList = (ArrayList)temp.clone();
           
            vector.add((ArrayList) temp.clone());

            temp.clear();
        }
       
        return vector;
    }
   
   
    public static int getFactorial (int n) {
       
        int result;
       
        if(n==1||n==0)
           
            return 1;

        result = getFactorial(n-1)*n;
       
        return result;
    }


Para utilizar el código, por ejemplo:

int numberOfPermutations = getFactorial(lista.size());
       
        ArrayList> permutations = permutar(lista, numberOfPermutations);
       
        System.out.println("Permutaciones resultantes: ");
       
        for(int i=0 ; i           
            System.out.println(permutations.get(i));
        }

Aclaraciones:

1. Tengo mucha prisa. He adaptado el código para lo que me hacía falta, sin tener ni pajorera idea de lo que está pasando en algunos sitios, por eso igual encontráis algún gazapo. Lo que os puedo decir es que funcionar, funciona (y si veis que no, avisad). Yo en general sólo me fío de mi código, pero si hay prisa, hay prisa.

2. Sí, cuando me aburrí de poner nombres como "aux" y "temp", empecé con los vegetales. Creo que en el código hay una patata y una zanahoria.

3. No estáis queriendo lo suficiente a Jairo. Queredle más.

Aquí queda esto, por si alguien desesperado lo encuentra vagando por internet y lo puede usar, y sobre todo, por si la preparo con el proyecto y tengo que recuperar el código.

Dulces sueños y no programéis, que luego os volvéis como yo.

p.d. Espero haberme explicado decentemente, es tarde y llevo todo el día programando esta historia, así que estoy un poco espesa. Si algo no se entiende, me lo decís en los comentarios o me mandáis un email.