Anagrama en C++

¿se considera anagrama simplemente si tienen exactamente las mismas letras pero en otro orden o deben cumplir alguna regla mas?

En cualquier caso varias soluciones se me ocurren:

Calcular los anagramas de la 1ª palabra y para cada uno que se encuentre se comprueba si es la 2ª palabra, en cuanto uno sea igual es pq es anagrama.

Crearte 2 palabras auxiliares y en cada una de ellas ordenar alfabéticamente las letras de una palabra. Comparar las 2 auxiliares y si son iguales son anagramas.

Ej: 1 - ababab, 2 - bbbaaa
aux1 - aaabbb, aux2 - aaabbb

Para cada palabra, contar en nº de veces que sale cada letra y comparar el resultado.

Esas se me ocurren sin pensarlo demasiado.

vector de enteros indexado con caracteres inicializado a 0.
{a..z}
Recorres la primera palabra y sumas +1 en cada caracter q veas. v[caracter]= v[caracter]+1;
Recorres la segunda palabra y le restas 1 de la misma forma de antes.
Buscas algo distinto de 0 en el vector y ya esta.

O(2n + 27)

Si puedes tener mayusculas y minusculas, recorres el vector transformandolo todo a minusculas o mayusculas a tu gusto, seria (3n +27 ) tampoco es tanta la diferencia.

Ordenar alfabeticamente es O(n·logn) con Hoare.

Haces la funcion "<=" ( a, b: Caracter ) dev boolean.
y metes el algoritmo de hoare y gl.

Lo tengo en ADA pero te lo traduzco a C lo mejor posible, no se traducir el t'first y t'last.





/* --------------------------------------------------- /
void intercambia(char &x,&y) is
/ --------------------------------------------------- */
char aux;
{
aux := *x; *x := *y; *y := aux;
}

void ordenacionPorHoare(Tabla t) is
/* Pre: cierto
-- Post: PT alfa en {t'first..t'last-1}.t(alfa) <= t(alfa+1)
------------------------------------------------------ */
int i, s; int pivote;
{

  if t'first < t'last then
   {  pivote = 'k';
     i = t'first + 1;
     s = t'last;
     while ( i < s + 1 ) {
        if (( t[i] <= pivote )  then
          { i = i + 1; }
        else
         {if pivote <= t[s] then
           {s:= s - 1;}
        else
           {intercambia(&t[i], &t[s]);
           i := i + 1;  s := s - 1;
        }}
     }
     intercambia(t[t'first], t[s]);
     ordenacionPorHoare( t[t'first..s-1] );
     ordenacionPorHoare( t[s+1..t'last]  );
  }

}
[/i]

Yo me decantaria por la primera opcion y no meterte con ordenaciones de ningun tipo, total es 1 vectorcito de tamaño 27, es del orden de (2·n + 27) lo cual esta muy bien.

Ya esta, ya lo tengo!
Con esa ideas que me disteis he conseguido que funcionara (almenos con todos los juegos de pruebas que dejo el profesor).

El codio lo podeis ver aquí:
http://rafb.net/paste/results/whJmNz49.html

En cuanto a #4 no entendí mucho el script, supongo que no tendré suficiente nivel como para "ver lo que hace", he emepzado este año con la programación y con lo que llevamos hecho aún no había visto estas funciones.

El ejercicio estaba pensado para practicar el diseño descendiente.

Un saludo y gracias por la ayuda

PD: las explicaciones estan en catalan, si no entendeis algo avisar y os lo comento.

A ver el QuickSort basicamente lo que hace es separar el conjunto te datos en 2 mas pekeños, y hacer la llamada recursiva a si mismo para recorrer cada una de las 2 mitades.

Has hecho recursividad?

Pues bueno, asi rapidamente:

Una funcion recursiva es una funcion que en algun momento de su ejecucion se llama a sí misma.

Por ejemplo:

funcion Func1 ( param1, param2) devuelve entero{
....entero i;
....//Codigo...
....i = Func1 ( nuevoParam1, nuevoParam2);
....//Codigo
.... devuelvo i;
}

no son permutaciones?