Palabras cíclicas
Planteamiento del problema
Podemos pensar en una palabra cíclica como una palabra escrita en un círculo. Para representar una palabra cíclica, elegimos una posición de inicio arbitraria y leemos los caracteres en el sentido de las agujas del reloj. Entonces, "imagen" y "turepic" son representaciones para la misma palabra cíclica.
Se le da una cadena de palabras [], cada elemento de los cuales es una representación de una palabra cíclica. Devuelve el número de diferentes palabras cíclicas que se representan.
Victorias más rápidas (Big O, donde n = número de caracteres en una cadena)
word-puzzle
counting
fastest-algorithm
piernas de eggon
fuente
fuente
Respuestas:
Pitón
Aquí está mi solución. Creo que todavía podría ser O (n 2 ), pero creo que el caso promedio es mucho mejor que eso.
Básicamente funciona normalizando cada cadena para que cualquier rotación tenga la misma forma. Por ejemplo:
La normalización se realiza buscando el carácter mínimo (por código de caracteres) y girando la cadena para que ese carácter esté en la última posición. Si ese carácter aparece más de una vez, se utilizan los caracteres después de cada aparición. Esto le da a cada palabra cíclica una representación canónica, que puede usarse como clave en un mapa.
La normalización es n 2 en el peor de los casos (donde cada carácter de la cadena es el mismo, por ejemplo
aaaaaa
), pero la mayoría de las veces solo habrá unas pocas ocurrencias, y el tiempo de ejecución estará más cercan
.En mi computadora portátil (Intel Atom de doble núcleo a 1.66 GHz y 1 GB de RAM), ejecutar esto
/usr/share/dict/words
(234,937 palabras con una longitud promedio de 9.5 caracteres) toma alrededor de 7.6 segundos.fuente
Python (3) otra vez
El método que utilicé fue calcular un hash rodante de cada palabra comenzando en cada carácter de la cadena; Como es un hash rodante, se necesita tiempo O (n) (donde n es la longitud de la palabra) para calcular todos los n hashes. La cadena se trata como un número base-1114112, lo que garantiza que los hashes sean únicos. (Esto es similar a la solución de Haskell, pero más eficiente ya que solo pasa por la cadena dos veces).
Luego, para cada palabra de entrada, el algoritmo verifica su hash más bajo para ver si ya está en el conjunto de hashes vistos (un conjunto de Python, por lo tanto, la búsqueda es O (1) en el tamaño del conjunto); si es así, entonces la palabra o una de sus rotaciones ya se ha visto. De lo contrario, agrega ese hash al conjunto.
El argumento de la línea de comandos debe ser el nombre de un archivo que contiene una palabra por línea (como
/usr/share/dict/words
).fuente
Haskell
No estoy seguro de la eficacia de esto, lo más probable es que sea bastante malo. La idea es crear primero todas las rotaciones posibles de todas las palabras, contar los valores que representan de forma única las cadenas y seleccionar el mínimo. De esa forma obtenemos un número que es exclusivo de un grupo cíclico.
Podemos agrupar por este número y verificar el número de estos grupos.
Si n es el número de palabras en la lista ym es la longitud de una palabra, entonces calcular el 'número de grupo cíclico' para todas las palabras es
O(n*m)
, ordenarO(n log n)
y agruparO(n)
.fuente
Mathematica
Decidí comenzar de nuevo, ahora que entiendo las reglas del juego (creo).
Un diccionario de 10000 palabras de "palabras" únicas compuestas al azar (solo minúsculas) de longitud 3. De manera similar, se crearon otros diccionarios que consisten en cadenas de longitud 4, 5, 6, 7 y 8.
g
toma la versión actual del diccionario para verificar. La palabra superior se une con variantes cíclicas (si existe alguna). La palabra y sus coincidencias se agregan a la lista de salidaout
de palabras procesadas. Las palabras de salida se eliminan del diccionario.f
recorre todas las palabras del diccionario.Ejemplo 1 : palabras reales
Ejemplo 2 : palabras artificiales. Diccionario de cadenas de longitud 3. Primero, sincronización. Luego el número de palabras del ciclo.
Tiempos en función de la longitud de la palabra . 10000 palabras en cada diccionario.
No sé cómo interpretar los resultados en términos de O. En términos simples, el tiempo se duplica aproximadamente del diccionario de tres caracteres al diccionario de cuatro caracteres. El tiempo aumenta de manera insignificante de 4 a 8 caracteres.
fuente
Esto se puede hacer en O (n) evitando el tiempo cuadrático. La idea es construir el círculo completo atravesando la cadena base dos veces. Así que construimos "amazingamazin" como la cadena de círculo completo para verificar todas las cadenas cíclicas correspondientes a "amazing".
A continuación se muestra la solución Java:
fuente
No sé si esto es muy eficiente, pero esta es mi primera grieta.
fuente
Perl
No estoy seguro de entender el problema, pero esto coincide con el ejemplo @dude publicado en los comentarios al menos. por favor corrija mi análisis seguramente incorrecto.
para cada palabra W en las N palabras dadas de la lista de cadenas, debe recorrer todos los caracteres de W en el peor de los casos. Tengo que asumir que las operaciones hash se realizan en tiempo constante.
fuente