Autor Tema: Generar anagramas  (Leído 598 veces)

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
Generar anagramas
« : febrero 04, 2010, 09:35:27 pm »
Bueno hoy tuve que hacer un codigo para un reto de euler 183, y se me ocurrio hacer paper, porque no es un algoritmo muy comun ;), o si lo es HPTA no se encuentra!!!!!!!...

Es para ver si dos palabras son anagramas o no y a la vez es para crear los anagramas de una palabra ;)

Bueno primero que todo, como saber si dos palabras son anagramas entre si????...pos bueno

Anagrama: es una palabra que contiene exactamente las mismas letras que otra pero en un orden diferente...

ejemplo:  phicar


jajaj bueno como eso sucede entonces que reglas deben tener?

-> deben tener la misma longitud, asi que si no la tienen pos no nos interesa ;)
->deben tener la misma cantidad de repeticiones de letra, si una tiene 2 'o' pues la otra la misma historia ;)

Como hacemos eso programando?

-> la primera regla pos se deduce facil tienen la misma longitud las cadenas ;)
-> aca recorremos una cadena y le vamos sacando las letras, contamos y tiene que ser la misma cantidad en ambas ;)

--------------------------------------------------------------

Como p$#%^&*( generamos los anagramas?

primero que todo sabemos como saber cuantos anagramas puede tener una palabra??

sencillo, si la paalabra no tiene letras repetidas va a ser simplemente el factorial de la longitud...ya que es como si permutaramos asi (nPn) = n! ;)  solo notacion matematica :P...

pero merda y si queremos saber los posibles anagramas de "perro"????, pos no son 120 ya que una letra se repite 2 veces pos sencillo cogemos cada letra ;) y multiplicamos ;)  pero ahora combinamos ;)...esa se las dejo de tarea, el caso es que de perro son 60 ;) (5C1)(4C1)(3C2)(1C1) ;)


Jajajaj ahora si lo que nos interesa, el algoritmo...lo primero que pense fue en ir alternando la ultima letra y pasarla por la primera

ej:

in-->ni
phicar->rphica->arphic->carphi->icarph->hicarp

y asi podriamos hacerlo recursivamente de la siguiente manera

ej: formas anagramas 123

123
   32
312
   21
231
   13

y formariamos 6 ;), que son todos los anagramas de 123...

ese es el algoritmo es recursivo y no lo explote mucho ya que me sirvio pa el reto ;)...ahi se los dejo

Código: (java) [Seleccionar]
import java.util.*;
public class Anagrama{
public static void main(String args[]){
if(args.length==2){
if(Anag(args[0],args[1]))
System.out.println(args[1]+" es anagrama de "+args[0]);
else
System.out.println(args[1]+" NO es anagrama de "+args[0]);
}else if(args.length==1){
String genAr=GenAna("",args[0]);
String epa = "";
StringTokenizer e=new StringTokenizer(genAr,",");
String tmp="";
Vector<String>pp = new Vector<String>();
while(e.hasMoreTokens()){
if(((tmp=e.nextToken()).length()==args[0].length())&&!(pp.contains(tmp))){
pp.add(tmp);
epa+=tmp+";";
}
}
System.out.println(epa);

}else
System.err.println("Nada!");
}
public static String GenAna(String q,String a){
String tmp= "";
if(a.length()<2)return "";
for(int n = 0;n<a.length();n++){
a=a.substring(1,a.length())+a.charAt(0);
tmp+=(q+a)+","+GenAna(q+""+a.charAt(0)+"",a.substring(1,a.length()))+",";
}
tmp = tmp.substring(0,tmp.length()-1);
return tmp;
}
public static boolean Anag(String a,String b){
if(a.length()!=b.length())return false;
for(int n = 0;n<a.length();n++)
if(Vec(a,a.charAt(n))!=Vec(b,a.charAt(n)))
return false;
return true;
}
public static int Vec(String a,char b){
int p=0,v=0;
while((p=a.indexOf(b,p))!=-1){
p++;
v++;
}
return v;
}
}


Un abrazo ;)
:)

my.opera.com/phicar

Phicar

  • :P
  • Administrador
  • Mensajes: 283
  • (1+sqrt(5))/2
    • MSN Messenger - diego_villahacker@hotmail.com
    • Ver Perfil
    • Phicar's Blog
    • Email
Re: Generar anagramas
« Respuesta #1 : febrero 16, 2010, 02:03:24 pm »
Hola, Gracias a mi super estudio en la universidad xDDDDDDDDDDDDDDDDDDDDDDDD he estado viendo videos de programacion de Stanford, con tan buena suerte que me tope con este, la nena usa mi mismo metodo, solo que a ella se le ve bonito xDDDD porque no lo tuvo que listar, sino solo los imprimio xDDD


http://academicearth.org/lectures/refresh-permute-code
:)

my.opera.com/phicar

4ng3r

  • IQ
  • Mensajes: 145
    • Ver Perfil
    • 4ng3r Blog
    • Email
Re: Generar anagramas
« Respuesta #2 : abril 23, 2010, 02:41:55 pm »
huy mk tremenda pagina