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)
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: