Escribir permutaciones en Java

De ChuWiki
Saltar a: navegación, buscar

Vamos a ver aquí un pequeño ejemplo de cómo se pueden escribir las permutaciones de una serie de elementos por pantalla usando recursividad.

Supongamos que metemos nuestra colección de elementos en una lista, de esta manera

LinkedList<Character> conjunto =new LinkedList<Character>();
conjunto.add('1');
conjunto.add('2');
conjunto.add('3');
conjunto.add('4');
conjunto.add('5');

El algoritmo recursivo es fácil. Hacemos un bucle para recorrer los elementos. Para cada elmento, debemos escribir las permutaciones de los demás anteponiendo el elemento elegido. Es decir, imaginemos que cogemos el '1'. Simplemente hay que hacer las permutaciones de los demás poniendo delante ese '1'. Luego cogemos el '2' y hay que hacer las permutaciones de los demás (incluido el '1') anteponiendo ese '2' y así sucesivamente.

La recursividad acaba cuando la lista sólo tiene un elemento, en el que tendremos que escribir lo anterior más el elemento. El código java puede ser así

public class Permutaciones
{
    public static void main(String[] args) {
        LinkedList<Character> conjunto =new LinkedList<Character>();
        conjunto.add('1');
        conjunto.add('2');
        conjunto.add('3');
        conjunto.add('4');
        conjunto.add('5');
        
        escribe ("", conjunto);
    }

    public static void escribe(String a, LinkedList<Character> conjunto) {
        if (conjunto.size()==1)
        {
            System.out.println(a+conjunto.get(0));
        }
        for (int i=0;i<conjunto.size();i++)
        {
            Character b = conjunto.remove(i);
            escribe (a+b, conjunto);
            conjunto.add(i,b);
        }
    }
}

El String que vamos pasando al método le sirve al método para saber que tiene que escribir ese String delante de cada una de las permutaciones que genere. Si la lista tiene un elemento, escribe el String seguido de ese elemento. Si tiene más, hace un bucle para los elementos que quedan y para cada uno de ellos

  • retira el elemento de la lista
  • añade el elemento al String
  • se llama recursivamente a sí mismo
  • restaura la lista poniendo el elemento que había quitado.