2.4. Un ejemplo de detección de anagramas

Un buen problema de ejemplo para mostrar algoritmos con diferentes órdenes de magnitud es el clásico problema de detección de anagramas para cadenas de caracteres. Una cadena es un anagrama de otra si la segunda es simplemente un reordenamiento de la primera. Por ejemplo, 'fresa' y 'frase' son anagramas. Las cadenas 'caro' y 'roca' son también anagramas. Por razones de simplicidad, asumiremos que las dos cadenas en cuestión son de la misma longitud y que están formadas por símbolos del conjunto de 26 caracteres alfabéticos en minúsculas. Nuestro objetivo es escribir una función booleana que tomará dos cadenas y devolverá una confirmación de si son o no anagramas.

2.4.1. Solución 1: Marcado de verificación

Nuestra primera solución al problema de los anagramas verificará que cada carácter de la primera cadena realmente aparezca en la segunda. Si es posible “marcar” todos los caracteres, entonces las dos cadenas deben ser anagramas. El marcado de verificación de un carácter se realizará reemplazándolo con el valor especial de Python None. No obstante, como las cadenas en Python son inmutables, el primer paso en el proceso será convertir la segunda cadena en una lista. Cada carácter de la primera cadena se puede verificar contra los caracteres de la lista y, si se encuentra, se marca mediante el reemplazo. El ActiveCode 1 muestra esta función.

Para analizar este algoritmo, debemos tener en cuenta que por cada uno de los n caracteres en cadena1 se causará una iteración a lo largo de hasta n caracteres en la lista de cadena2. Cada una de las n posiciones de la lista se visitará una vez para compararla con un carácter de cadena1. El número de visitas se convierte entonces en la suma de los enteros de 1 a n. Dijimos anteriormente que esto puede escribirse como

\[\begin{split}\sum_{i=1}^{n} i &= \frac {n(n+1)}{2} \\ &= \frac {1}{2}n^{2} + \frac {1}{2}n\end{split}\]

A medida que \(n\) se hace más grande, el término \(n^{2}\) dominará el término \(n\) y el \(\frac {1} {2}\) puede ignorarse. Por lo tanto, esta solución es \(O(n^{2})\).

2.4.2. Solución 2: Ordenar y comparar

Otra solución al problema de los anagramas hará uso del hecho de que aunque cadena1 y cadena2 son diferentes, serán anagramas solamente si consisten exactamente de los mismos caracteres. Por lo tanto, si empezamos por clasificar cada cadena alfabéticamente, de la a a la z, terminaremos con la misma cadena si las dos originales son anagramas. El ActiveCode 2 muestra esta solución. De nuevo, en Python podemos aplicar el método incorporado sort sobre listas simplemente convirtiendo al principio cada cadena en una lista.

A primera vista usted podría pensar que este algoritmo es \(O(n)\), ya que hay una sola iteración para comparar los n caracteres después del proceso de ordenamiento. Sin embargo, las dos llamadas al método sort de Python no carecen de su propio costo. Como veremos en un capítulo posterior, ordenar es típicamente \(O(n^{2})\) u \(O(n\log n)\), por lo que las operaciones de ordenamiento dominan la iteración. Al fin y al cabo, este algoritmo tendrá el mismo orden de magnitud que aquél del proceso de ordenamiento.

2.4.3. Solución 3: Fuerza bruta

Una técnica de fuerza bruta para resolver un problema normalmente intenta agotar todas las posibilidades. Para el problema de detección de anagramas, podemos simplemente generar una lista de todas las cadenas posibles usando los caracteres de cadena1 y luego ver si se produce cadena2. Sin embargo, hay una dificultad con este enfoque. Cuando se generan todas las cadenas posibles de cadena1, hay n posibles primeros caracteres, \(n-1\) posibles caracteres para la segunda posición, \(n-2\) para la tercera, y así sucesivamente. El número total de cadenas candidatas es \(n*(n-1)*(n-2)*...*3*2*1\), lo cual es \(n!\). Aunque algunas de las cadenas pueden ser versiones duplicadas, el programa no puede saber esto de antemano y por tanto generá de todos modos \(n!\) cadenas diferentes.

Resulta que \(n!\) crece aún más rápido que \(2^{n}\) a medida que n se hace grande. De hecho, si cadena1 tuviera una longitud de 20 caracteres, habría \(20!=2,432,902,008,176,640,000\) cadenas candidatas posibles. Si procesáramos una posibilidad cada segundo, aún así nos tomaría 77,146,816,596 años el recorrido de la lista completa. Esto probablemente no va a ser una buena solución.

2.4.4. Solución 4: Contar y comparar

Nuestra última solución al problema de los anagramas se aprovecha del hecho de que cualesquiera dos anagramas tendrán el mismo número de letras a, el mismo número de letras b, el mismo número de letras c, y así sucesivamente. Para decidir si dos cadenas son anagramas, primero vamos a contar el número de veces que se produce cada caracter. Puesto que hay 26 caracteres posibles, podemos usar una lista de 26 contadores, uno para cada caracter posible. Cada vez que veamos un caracter en particular, vamos a incrementar el contador en esa posición. Al terminar, si las dos listas de contadores son idénticas, las cadenas deben ser anagramas. El ActiveCode 3 muestra esta solución.

Nuevamente, la solución tiene varias iteraciones. Sin embargo, a diferencia de la primera solución, ninguna de ellas está anidada. Las dos primeras iteraciones utilizadas para contar los caracteres están ambas basadas en n. La tercera iteración, que compara las dos listas de conteos, siempre toma 26 pasos ya que hay 26 caracteres posibles en las cadenas. La suma de todo nos da \(T(n)=2n+26\) pasos. Es decir \(O(n)\). Hemos encontrado un algoritmo de orden de magnitud lineal para resolver este problema.

Antes de dejar este ejemplo, necesitamos decir algo sobre los requisitos de espacio. Aunque la última solución pudo ejecutarse en tiempo lineal, sólo pudo hacerse mediante el uso de almacenamiento adicional para mantener las dos listas de conteo de caracteres. En otras palabras, este algoritmo sacrificó espacio para ganar tiempo.

Esto ocurre con frecuencia. En muchas ocasiones usted tendrá que tomar decisiones sobre los sacrificios mutuos entre tiempo y espacio. En este caso, la cantidad de espacio adicional no es significativa. Sin embargo, si el alfabeto subyacente tuviera millones de caracteres, habría más preocupación. Como científico de la computación, cuando deba tomar una decisión entre algoritmos, le corresponde a usted determinar el mejor uso de los recursos computacionales dado un problema particular.

Autoevaluación

You have attempted of activities on this page