A recent tweet by Fermat's Library noted that the Fundamental theorem of arithmetic provides a novel (if inefficient) way of determining whether two words are anagrams of one another.
The Fundamental theorem of arithmetic states that every integer greater than 1 is either a prime number itself or can be represented as the unique product of prime numbers.
First, one assigns distinct prime numbers to each letter (e.g. a=2, b=3, c=5, ...). Then form the product of the numbers corresponding to each letter in each of the two words. If the two products are equal, the words are anagrams. For example,
'cat': $5 \times 2 \times 71 = 710$
'act': $2 \times 5 \times 71 = 710$
The following code implements and tests this algorithm.
from functools import reduce
a = 'abcdefghijklmnopqrstuvwxyz'
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
71, 73, 79, 83, 89, 97, 101]
d = dict(zip(a, p))
def prod(s):
return reduce((lambda n1, n2: n1*n2), [d[lett] for lett in s])
def is_anagram(s1, s2):
return prod(s1) == prod(s2)
Here, d is a dictionary mapping the letters to their primes. The functools.reduce method applies a provided function cumulatively to the items of a sequence.
To see that it works, try:
is_anagram('cat', 'act')
True
is_anagram('tea', 'tee')
False
Note that for longer words the products formed get quite large:
prod('floccinaucinihilipilification')
35334111214198884032311058457421182500
Comments
Comments are pre-moderated. Please be patient and your comment will appear soon.
Dominik Stańczak 5 years, 1 month ago
This is utterly dreadful and I love it. Clever idea!
Link | ReplyNew Comment