jueves, mayo 23, 2013

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.

18 comentarios:

  1. Tía, no entiendo nada. Y lo que es peor... me importa un carajo!! Termina el proyecto de una vez que así no vamos a irnos al caribe nunca!! termina y vuelve a hablar de cosas normales como cuentos gore o... vale, igual no son normales, pero son más amenas.

    Por cierto... quiero saber tu opinión sobre peter pan... :) porfis, porfis....
    Un beso!!

    ResponderEliminar
    Respuestas
    1. Que no te interese demuestra que aún te queda algo de estabilidad mental, te felicito.
      Peter Pan, vale, me lo apunto ;)

      Eliminar
  2. Te diría que lo bueno de la recursividad es que una vez la has entendido ya no la olvidas nunca, pero es mentira. Yo ya no me acuerdo de un pimiento :P

    ResponderEliminar
    Respuestas
    1. A mí me lo vas a contar; yo recuerdo hacer programas recursivos hace tiempo sin mucho drama, y ahora no me acuerdo de nada. Jo, con lo lista que me sentía yo cuando la manejaba bien.

      Eliminar
  3. Te prometo que lo he intentado, pero he tenido que irme a aprender a cocinar...

    ResponderEliminar
    Respuestas
    1. Sabia decisión. Besitos varios por el intento :)

      Eliminar
  4. Tú eres grande... Me engatusas con el enlace a mi blog para que me sienta culpable y te lea... ¡Pues no! Que sepas que te leo porque quiero y porque me gusta leerte y no por el chantaje emocional. Y eso que no tengo ni la más remota idea de lo que has estado hablando más allá de que te has ahorrado ocho días por el trabajo de Jairo Alonso. ¡Viva Jairo Alonso pues!

    ResponderEliminar
    Respuestas
    1. ¡MUAHAHAHAHA CHANTAJE EMOCIONAL! Que no, hombre, que lo pongo porque me da la gana, faltaría más... lo importante de todo esto es que quieras mucho al tal Jairo, el resto es todo irrelevante :D

      Eliminar

  5. Jum... eres la única ingeniera que conozco que me cae bien, Key. Matemáticamente, la idea es sencilla (¿usas la función Gamma para calcular el número final de permutaciones, no?). Supongo de forma intuitiva (no me he puesto con el código porque ahí me volvería más idiota de lo que ya soy) que la modificación consistió en considerar que, siendo la lista de caracteres x1,x2,x3,...,xn, introducir en cada xi (con i entre 1 y n) como una cadena de caracteres (y1,...,yk), (z1,...zk), etc. A lo mejor me hice un supremo lío, pero así lo entiendo yo. Lo que no entiendo es si la función también permuta los caracteres de las listas de listas de caracteres que está permutando en principio, porque no creo que sea eso lo que tú quieras, ¿o no? Y odio la recursividad, principalmente porque no la entiendo :P

    Au, esta entrada es tierna.

    P.S. Sobre lo que dice Naar, investiga a los psicopompos en relación con Peter Pan. Puede salir algo mucho más serio que hacer coña, pero igual hasta es interesante. ¡Mucha mierda con el proyecto! N.

    ResponderEliminar
    Respuestas
    1. No sabía lo que era la función gamma; he visto que es como el factorial pero para números complejos... mis números, afortunadamente, de complejos no tienen nada, porque si fuera así me volvería loca del todo, así que no la utilizo. Mi función no permuta los caracteres de las listas, porque entonces no se entendería nada. Y yo también odio la recursividad.

      Leí Peter Pan en su día y recuerdo que me dio mal rollo. Cuando tenga un rato, me lo vuelvo a leer y os cuento.

      Eliminar
  6. Entonces, con tu código puedo hacer tortilla de patatas, no? Bien, ya estaba hasta los mismísimos de chamuscarme los dedos con el aceite.

    Ale, a cenar tortilla todo el mundo! xD

    ResponderEliminar
    Respuestas
    1. Mira, con lo inútil que soy yo cocinando, igual la solución es crear un algoritmo para cada plato, a lo mejor funciona :D

      Eliminar
  7. ¿Si no entendemos algo, dices? Y si no entendemos nada de nada... ¿qué hacemos? Me alegro de que hayas dado con Jairo. Tu vida ya no será la misma a partir de esto. Y no sé qué más decir. Sé lo que es una zanahoria y también una patata. Del resto... pues más bien nada. Besotes!!!

    ResponderEliminar
    Respuestas
    1. Jajajajaja besos para ti también por leer esta cosa infernal. No te creas que yo entiendo mucho más que lo de la patata y la zanahoria. La recursividad es un lío.

      Eliminar
  8. Esta entrada tuya me recuerda a mi clase de econometria, que nada tiene que ver excepto en que todo eran cosas raras escritas en chino.
    Suerte con el proyecto!

    ResponderEliminar
    Respuestas
    1. Me parece que lo que sabes tú de recursividad es lo que sé yo de econometría... Por qué no nos meteremos en cosas más sencillas, si es que parecemos bobas xD

      Eliminar
  9. Me gusta más cuando explicas cuentos gores, soy asín...

    ResponderEliminar