Palavras cíclicas
Declaração do Problema
Podemos pensar em uma palavra cíclica como uma palavra escrita em círculo. Para representar uma palavra cíclica, escolhemos uma posição inicial arbitrária e lemos os caracteres no sentido horário. Portanto, "imagem" e "turepic" são representações para a mesma palavra cíclica.
Você recebe as palavras String [], cada elemento do qual é uma representação de uma palavra cíclica. Retorne o número de palavras cíclicas diferentes que são representadas.
Vitórias mais rápidas (Big O, onde n = número de caracteres em uma string)
word-puzzle
counting
fastest-algorithm
eggonlegs
fonte
fonte
Respostas:
Pitão
Aqui está a minha solução. Acho que ainda pode ser O (n 2 ), mas acho que o caso médio é muito melhor que isso.
Basicamente, ele funciona normalizando cada string para que qualquer rotação tenha a mesma forma. Por exemplo:
A normalização é feita procurando o caractere mínimo (por código char) e girando a string para que o caractere esteja na última posição. Se esse caractere ocorrer mais de uma vez, serão utilizados os caracteres após cada ocorrência. Isso fornece a cada palavra cíclica uma representação canônica, que pode ser usada como uma chave em um mapa.
A normalização é n 2 no pior caso (onde todos os caracteres da string são iguais, por exemplo
aaaaaa
), mas na maioria das vezes haverá apenas algumas ocorrências e o tempo de execução será mais próximon
.No meu laptop (Intel Atom dual core de 1,66 GHz e 1 GB de RAM), a execução
/usr/share/dict/words
(234.937 palavras com um comprimento médio de 9,5 caracteres) leva cerca de 7,6 segundos.fonte
Python (3) novamente
O método que eu usei foi calcular um hash de rolagem de cada palavra começando em cada caractere na string; como é um hash contínuo, o O (n) (onde n é o comprimento da palavra) leva tempo para calcular todos os n hashes. A sequência é tratada como um número base-1114112, o que garante que os hashes sejam exclusivos. (Isso é semelhante à solução Haskell, mas mais eficiente, pois só passa pela cadeia de caracteres duas vezes.)
Então, para cada palavra de entrada, o algoritmo verifica seu hash mais baixo para ver se ele já está no conjunto de hashes visto (um conjunto Python, portanto, a pesquisa é O (1) no tamanho do conjunto); se for, a palavra ou uma de suas rotações já foi vista. Caso contrário, ele adiciona esse hash ao conjunto.
O argumento da linha de comando deve ser o nome de um arquivo que contém uma palavra por linha (como
/usr/share/dict/words
).fonte
Haskell
Não tenho certeza sobre a eficiência disso, provavelmente muito ruim. A idéia é criar primeiro todas as rotações possíveis de todas as palavras, contar os valores que representam exclusivamente as seqüências e selecionar o mínimo. Dessa forma, obtemos um número exclusivo para um grupo cíclico.
Podemos agrupar por esse número e verificar o número desses grupos.
Se n for o número de palavras na lista e m for o comprimento de uma palavra, calcule o 'número do grupo cíclico' para todas as palavras
O(n*m)
, classificandoO(n log n)
e agrupandoO(n)
.fonte
Mathematica
Decidi começar de novo, agora que entendo as regras do jogo (acho).
Um dicionário de 10000 palavras de "palavras" únicas compostas aleatoriamente (somente em minúsculas) de comprimento 3. De maneira semelhante, outros dicionários foram criados, consistindo em cadeias de comprimento 4, 5, 6, 7 e 8.
g
leva a versão atual do dicionário para verificar. A palavra superior é associada a variantes cíclicas (se houver alguma). A palavra e suas correspondências são anexadas à lista de saídaout
, de palavras processadas. As palavras de saída são removidas do dicionário.f
percorre o dicionário de todas as palavras.Exemplo 1 : palavras reais
Exemplo 2 : Palavras artificiais. Dicionário de cadeias de comprimento 3. Primeiro, tempo. Então o número de palavras do ciclo.
Tempos em função do comprimento da palavra . 10000 palavras em cada dicionário.
Não sei particularmente como interpretar as descobertas em termos de O. Em termos simples, o tempo praticamente dobra do dicionário de três caracteres para o dicionário de quatro caracteres. O tempo aumenta quase de forma insignificante de 4 a 8 caracteres.
fonte
Isso pode ser feito em O (n), evitando o tempo quadrático. A idéia é construir o círculo completo atravessando a corda base duas vezes. Então, construímos "amazingamazin" como a sequência de círculos completa para verificar todas as seqüências cíclicas correspondentes a "amazing".
Abaixo está a solução Java:
fonte
Não sei se isso é muito eficiente, mas esse é meu primeiro crack.
fonte
Perl
Não sei se entendi o problema, mas isso corresponde ao exemplo @dude postado nos comentários pelo menos. corrija minha análise certamente incorreta.
para cada palavra W nas N palavras fornecidas da lista de cadeias, você deve percorrer todos os caracteres de W no pior caso. Eu tenho que assumir que as operações de hash são feitas em tempo constante.
fonte