Algoritmo para encontrar anagramas

Brandon Skerritt Blocked Unblock Seguir Seguindo 2 de janeiro

Encontrar anagramas de palavras não parece um problema difícil, mas tem uma solução interessante.

Um anagrama é uma palavra ou frase que pode ser transformada em outra palavra ou sentença. Elvis tem todas as mesmas letras que Vidas, então Elvis é um anagrama de Vidas.

A maneira como a maioria das pessoas resolveria imediatamente esse problema seria pegar uma palavra, passar por todas as palavras do dicionário e ver se as combinações de letras correspondem exatamente.

A maneira de fazer isso usará um multiconjunto . Conjuntos são como matrizes onde a ordem não importa e as repetições não são permitidas. Com um array, [a, b] não é o mesmo que [b, a]. Mas com um conjunto, (a, b) é o mesmo que (b, a).

Os conjuntos não permitem repetições. Então (a, a, a, a, a, b) é o mesmo que (b, a) – porque o primeiro conjunto seria transformado em (a, b).

Um multiset é um conjunto que permite repetições, mas a ordem não importa. Para este exemplo, vamos começar pequeno.

Com nosso exemplo, temos uma lista chamada dicionário onde cada item desse dicionário é uma palavra. Queremos descobrir quais dessas palavras são anagramas de “Elvis”, então o que fazemos é fazer um loop no dicionário da seguinte forma:

Nota: não é assim que os multisets funcionam em Python, mas estou usando principalmente isso para ilustrar um ponto. Você pode descobrir como os multisets funcionam aqui . Você, provavelmente.

Você está certo. Isso é muito lento. Funcionaria, mas temos 2 problemas. O primeiro problema é que a capitalização não fará os multisets iguais. O segundo problema é que mais espaços podem aparecer na sentença de saída do que na palavra original.

Como exemplo, “carne assada” é um anagrama de “coma para a BSE”.

Com duas frases como “roast beef” e “eat for BSE”, se as transformassemos em multisets, elas não seriam iguais devido à quantidade diferente de espaços. Há outra maneira de calcular se duas sentenças são anagramas uma da outra. O teorema fundamental dos estados aritméticos:

Cada inteiro é um número primo ou pode ser representado como o produto de números primos e, além disso, essa representação é única, a ordem dos fatores.

Números primos são números que possuem apenas dois fatores – o número em si e 1.

Se atribuirmos cada letra do alfabeto a um número primo, assim:

E assim por diante, então calcule o produto desses números esse número é único – por causa do teorema fundamental da aritmética.

Isso significa que, para um multiset de letras, o produto de números primos para cada letra nesse multiconjunto é único. Se duas palavras ou frases tiverem o mesmo número, essas duas palavras ou sentenças são anagramas umas das outras. Vamos ver um exemplo rápido, é “BAC” um anagrama de “A Bc”?

Determinar quais palavras são anagramas de outras palavras seria tão simples quanto criar um dicionário de {Word: Fatoração Primária} e então agrupar toda a fatoração primária.

Agora, dadas duas frases, podemos facilmente dizer se elas são anagramas umas das outras.

Gostou deste artigo? Conecte-se comigo nas mídias sociais para discutir todas as coisas relacionadas à ciência da computação ?

Twitter | Instagram | LinkedIn

Não se esqueça de clicar no botão ?clap? para mostrar a sua apreciação!

Eu não fui pago por escrever este artigo. Se você quiser me apoiar ou gostou deste artigo, sinta-se livre para me comprar uma xícara de chá ou algo abaixo ??

Pague Brandon Skerritt usando o PayPal.Me
Vá para paypal.me/BrandonSkerritt e digite o valor. Como é o PayPal, é fácil e seguro. Não tem um PayPal… www.paypal.me
Pague Brandon instantaneamente através Monzo.me
Toque no link para pagar o Brandon. Você não precisa criar uma conta e é totalmente gratuito. monzo.me