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.

El enebro: análisis

El Enebro (La Bella Durmiente y otros cuentos, Jacob y Wilhelm Grimm, cuentos completos II, editorial ANAYA), es un cuento que no conoce ni Cristo, soy consciente, pero cuando mencioné un trocito hace tiempo, la gente que comentó pareció interesada, así que bueno... yo lo cuento:

Tenemos un hombre muy rico casado con una mujer guapísima y maravillosa; son súper felices juntos, pero no pueden tener críos y eso les frustra un montón. La mujer un día se sienta bajo el enebro que tienen detrás de su casa y pide quedarse embarazada. Y como viene pasando en los cuentos de los Grimm, el árbol es mágico y le concede el deseo (no lo ponen así de claro, pero nos entendemos). La mujer pasa el embarazo súper contenta, pero al septimo mes enferma, y dos meses después tiene a su niño y se muere. Claro que no dicen que se muera por la enfermedad, sino:

"[...] dio a luz un  niño tan blanco como la nieve y tan rojo como la sangre; cuando lo vio, se sintió tan contenta, tan contenta, que se murió."

Morirse de estar muy contento muy contento. En fin.

El marido entierra a su mujer bajo el enebro, como ella deseaba, y un tiempo después se vuelve a casar, y con su nueva esposa tiene una niña.

Como todos estáis suponiendo, efectivamente la segunda esposa es una arpía sin alma. Quiere a su hija, pero el chaval le pone de los nervios, así que se dedica a hacerle la vida imposible mientras maquina algún sistema que le permita dejarle la herencia sólo a la niña.

A ver, a partir de aquí, la señora está poseída por el demonio. La realidad es que es un zorrón y que debería estar internada en algún sitio con unos barrotes gordísimos, pero bueno, los Grimm se sienten mejor si decimos que esto lo hace el diablo, así que el diablo será.

La niña le pide dos manzanas a su madre, una para ella y otra para su hermano. La madre, que sólo de pensar en darle algo al niño ya se está poniendo mala, le dice a su hija que por supuesto, que en cuanto el crío llegue del colegio, les da lo que ellos quieran. Cuando el chaval llega, su querida madrastra le ofrece la manzana, y el niño acepta. Entonces le dice que la coja de un baúl muy grande y con una cerradura muy afilada que tienen por allí, y cuando el niño está asomado para coger la fruta, la señora -recordemos la posesión infernal- le cierra la tapa en el cuello, decapita al crío, y ve rodar la cabeza entre las manzanas.

Muy bien todo.

Entonces a la madre le entra el pánico. Se da cuenta de que la ha liado pardísima, y con grandes arrepentimientos (no porque se sienta culpable por haber matado a un chavalín inocente, sino porque ve que la van a cazar y se va a comer el marrón de su vida), se va a su cuarto, coge un pañuelo blanco, y lo utiliza para atar la cabeza del niño de nuevo a su cuerpo. Coge al niño muerto, lo sienta en una silla con la manzana en la mano, el pañuelo al cuello, y aquí no ha pasado nada.

Me recuerda a una Barbie que tenía de pequeña. Se le rompió un trozo de cuello, así que se le caía la cabeza todo el rato. Yo la encasquetaba a presión, dejando a la muñeca casi sin cuello y dando como resultado una Barbie hawaiana de aspecto un pelín turbio.

Marlenita - así se llama la niña - ve a su hermano sentado con la manzana en la mano y nota algo raro, así que se va muy asustada a ver a su madre, para decirle que el niño está muy pálido, y que cuando le ha pedido la manzana que llevaba en la mano, él no ha contestado.

Haría hincapié en la cantidad de campos de la ciencia que han sido dañados irreparablemente al conseguir que un muchacho decapitado no sangre, si no fuera porque mi atención está ocupada con el hecho de que la madre le dice a su hija que si el crío no contesta, le dé un guantazo, consiguiendo con ello que Marlenita le arranque la cabeza de un manotazo a su hermano, y piense que ha sido ella la que le ha matado.

De todas las brujas desalmadas que he conocido leyendo a los Grimm, creo que esta petarda se lleva la palma.

¡Pero no queda así el tema!

La señora le dice a su hija que menos lloros, que si ya lo ha matado, no hay nada que hacer para arreglarlo, así que, por qué no, guisará al niño en el potaje.

¿Qué tal vamos por ahí? ¿Hemos vomitado ya? ¿No? ¡No pasa nada! ¡Hay más!

La mujer trocea al chaval y lo guisa en la cazuela, todo, faltaría más, delante de Marlenita. Cuando el padre llega a casa, su mujer le dice que el niño se ha ido a ver a su abuelo, que ya volverá. El padre se entristece mucho porque su hijo no le ha dicho adiós, y, como todo el mundo sabe, lo que hay que hacer cuando se está triste es comer.

Así que el tipo se zampa a su hijo - sin saberlo, claro está -, mientras alaba lo deliciosa que está la comida, y mientras va tirando los huesos de su hijo debajo de la mesa.

No me voy a volver a meter con la dieta Dukan en la vida.

Marlenita, que sigue pensando que ella ha matado a su hermanito, sigue llorando un montón, y se lleva los huesos, envueltos en un pañuelo de seda, al enebro. Allí aparece una niebla, con un fuego dentro, con un pájaro dentro, que desaparece llevándose consigo los huesos.

El pájaro se va volando y se posa sobre el tejado del orfebre, donde canturrea una canción horrorosa en la que declara que su madrastra le ha matado, su padre le ha comido, y su hermana ha dejado sus huesos bajo el enebro. El orfebre quiere escuchar ese espanto de canción otra vez porque dice que es muy bonita, y el pájaro le dice que quiere una cadena de oro a cambio. Con el trueque completado, el pájaro chungo se marcha con la cadena.

Siguiendo el mismo modelo de negocio consigue unos zapatos rojos del zapatero y una piedra de moler enorme de los molineros.

Entonces se marcha a casa a cantarle a su familia esa canción espantosa, y mientras la canta, le tira al cuello a su padre la cadena de oro, a su hermana los zapatos rojos a los pies, y a su madrastra la aplasta tirándole la piedra a la cabeza.

El niño resucita, todos están muy contentos, y colorín colorado, este cuento se ha acabado. Madrastra muerta, niño expájaro resucitado, aquí nadie hace preguntas, y a correr, que son dos días.

Hay que darle más fama a estos cuentos, por favor. Contádselos a vuestros hijos. Curtidlos desde pequeños. Provocadles traumas irreparables si hace falta.

Dulces sueños y no os asoméis a baúles afilados, que luego pasan cosas malas.