may 2 2010

Anagramas en Java

Un anagrama es una palabra que resulta de la transposición de las letras de otra palabra. Por ejemplo con ifx podemos obtener ifx,ixf,fix,fxi,xif,xfi (saber cuales de estas son palabras reales es un asunto totalmente distinto …). Hacer un programa en java para obtener todas estas posibles conjugaciones no es difícil, pero es interesante porque se requiere usar un método recursivo y esta clase de métodos tiende a seguir el patrón pocas líneas de código bastante dolor de cabeza. Esta es sólo una manera de solucionar un anagrama, debe de haber varias más.

import java.util.ArrayList;

public class Anagrama {
    private ArrayList<String> soluciones=new ArrayList<String>();

    public Anagrama(){  }

    public static void main(String args[]){
        Anagrama a=new Anagrama();
        String palabra="ifx";
        a.resolver(palabra);
        System.out.println(a.getSoluciones());
    }

    public void resolver(String palabra){
        palabra=palabra.toLowerCase();
        char[] letras=palabra.toCharArray();
        int tamanioPalabra=letras.length;
        int numeroIteraciones=0;
        char[] cadenaActual=new char[letras.length];
        resolver(letras,cadenaActual,tamanioPalabra,numeroIteraciones);
    }

    private void resolver(char[] letras,char[] cadenaActual,
            int tamanioPalabra,int numeroIteraciones){
        if (numeroIteraciones==tamanioPalabra){
            getSoluciones().add(new String(cadenaActual));
        }
        numeroIteraciones++;
        for(int i=0;i<tamanioPalabra;i++){
            if (letras[i]=='A'){
                //Como se paso todas las letras a minúscula, se usa "A"
                //para indicar que la letra en esa posición ya se utilizó,
                //de ser así sólo paso a la siguiente letra
            }else{
                char valorEliminado=letras[i];
                //valorEliminado es la letra que ya use y no
                //se debe seguir usando
                cadenaActual[numeroIteraciones-1]=valorEliminado;
                letras[i]='A';
                //Un valor q le doy para mostrar que ya lo elimine
                resolver(letras,cadenaActual,tamanioPalabra,numeroIteraciones);
                letras[i]=valorEliminado;
            }
        }
    }

    public ArrayList<String> getSoluciones() {
        return soluciones;
    }

    public void setSoluciones(ArrayList<String> soluciones) {
        this.soluciones = soluciones;
    }

}

By Diego • Java, Programación • 7 • Tags: , , ,