An algorithm to check if two words are anagrams - With example in Python

in #steemstem7 years ago

I like playing with mathematics and making algorithms. Recently, I saw the movie Shutter Island and saw the anagrams in the near-ending (okay, maybe this sentence is not relevant to the post).

Anyway, I thought of making an algorithm to test if two words are algorithms.


The Theory

Let there be a map/dictionary, A, where each letter from a to z is mapped to a positive prime integer. (For case sensitive checking, the capital letters are included.)

Example: A = {'a': 2, 'b': 3, 'c': 5, ....}

In both the words, the letters are swapped with the corresponding prime numbers, and made an array.

Example: cab becomes [5, 2, 3]. abc becomes [2, 3, 5]

All the elements inside the array is multiplied.

Example: The result for cab is 5×2×3=30 and for abc it is 2×3×5=30.

The Fundamental Theory of Arithmetic states that "the product of prime numbers is unique, apart from the order in which they occur". Therefore, for words that are anagrams, the product is the same, but for non-anagrams, it is always an unique integer.

This way, anagrams can be detected, even for very long words.


The Code (in Python)

Here is my minimal code:

import numpy as np
import string

WORDLIST = string.ascii_lowercase + " "

# `primes` finding code truncated. 
# `primes` is a set containing `len(WORDLIST)` prime numbers.

mapping = {}
for i in WORDLIST:
    mapping.update({i: primes.pop()})
print(mapping)

word_a = "Edward Daniels".lower()
word_b = "Andrew Laeddis".lower()
factor_a = np.array([mapping[i] for i in word_a])
factor_b = np.array([mapping[i] for i in word_b])

if np.prod(factor_a) == np.prod(factor_b):
    print("Words are anagrams!")
else:
    print("Nope, they're not.")



I truncated some part of the code — the part to find the primes. In the code,primes is a set containing the amount of prime numbers equal to len(WORDLIST). Here is the entire code, in case you need it.


I am new to blogging, and this was my first STEM post. If you like this, please upvote or resteem! Please share your reviews if you have any.