## Prime Anagrams

### October 15, 2019

There are many algorithms for recognizing anagrams. Here is an unusual one:

Assign each character to a prime number, then map a string to the corresponding primes, and compute their product. Two strings are anagrams only if they share a product.

Your task is to use prime numbers to recognize anagrams. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 12 Responses to “Prime Anagrams”

1. matthew said

Nice idea. Here we just use the first 26 primes to encode lowercase letters, and assign primes in the ETAOINSHRDLU order of frequency, keeping the size of the coding numbers relatively small:

import sys
import functools
import operator
primes = [5,71,41,29,2,47,61,19,7,97,79,31,43,13,
11,67,89,23,17,3,37,7,59,83,53,101]
def encode(s):
plist = (primes[ord(c)-ord('a')] for c in s)
return functools.reduce(operator.mul,plist,1)

codes = {}
for line in sys.stdin:
word = line.rstrip()
if all("a" <= c <= "z" for c in word):
codes.setdefault(encode(word),[]).append(word)

for n in sorted(codes.keys()):
s = codes[n]
if len(s) >= 7: print(n,sorted(s))

\$ python3 anagram.py < /usr/share/dict/words
261970 ['pares', 'parse', 'pears', 'rapes', 'reaps', 'spare', 'spear']
480930 ['carets', 'caster', 'caters', 'crates', 'reacts', 'recast', 'traces']

The highest code in that dictionary is “chlorofluorocarbons”, 8205628381610704807655035.

2. Daniel said

Here’s a solution in C using GMP.

// \$ gcc -o anagrams anagrams.c -lgmp

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include <gmp.h>

bool check_anagrams(char* s1, char* s2) {
static unsigned primes[] = {
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,  103,  107,  109,  113,  127,  131,
137,  139,  149,  151,  157,  163,  167,  173,  179,  181,  191,  193,  197,  199,  211,  223,
227,  229,  233,  239,  241,  251,  257,  263,  269,  271,  277,  281,  283,  293,  307,  311,
313,  317,  331,  337,  347,  349,  353,  359,  367,  373,  379,  383,  389,  397,  401,  409,
419,  421,  431,  433,  439,  443,  449,  457,  461,  463,  467,  479,  487,  491,  499,  503,
509,  521,  523,  541,  547,  557,  563,  569,  571,  577,  587,  593,  599,  601,  607,  613,
617,  619,  631,  641,  643,  647,  653,  659,  661,  673,  677,  683,  691,  701,  709,  719,
727,  733,  739,  743,  751,  757,  761,  769,  773,  787,  797,  809,  811,  821,  823,  827,
829,  839,  853,  857,  859,  863,  877,  881,  883,  887,  907,  911,  919,  929,  937,  941,
947,  953,  967,  971,  977,  983,  991,  997, 1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049,
1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163,
1171, 1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283,
1289, 1291, 1297, 1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423,
1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511,
1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597, 1601, 1607, 1609, 1613, 1619,
};
mpz_t prod1;
mpz_t prod2;
mpz_init(prod1);
mpz_init(prod2);
mpz_set_ui(prod1, 1);
mpz_set_ui(prod2, 1);
for (char* s = s1; *s != '\0'; ++s) {
mpz_mul_ui(prod1, prod1, primes[(unsigned)(*s)]);
}
for (char* s = s2; *s != '\0'; ++s) {
mpz_mul_ui(prod2, prod2, primes[(unsigned)(*s)]);
}
bool result = mpz_cmp(prod1, prod2) == 0;
mpz_clear(prod1);
mpz_clear(prod2);
return result;
}

int main(int argc, char* argv[]) {
if (argc != 3) return EXIT_FAILURE;
bool anagrams = check_anagrams(argv[1], argv[2]);
printf("%d\n", anagrams);
return EXIT_SUCCESS;
}

Example:

\$ ./anagrams programming praxis
0

\$ ./anagrams praxis xsairp
1

3. matthew said

That second ‘7’ in the list of primes should be ’73’!

4. Ernie said

If we use int for the product we will occasionally get overflow. I believe anagrams will still give the same product even with overflow but does anyone know whether two non anagrams can give the same product if overflow occurs during calculation of the product?

5. Daniel said

@Ernie, I believe it’s necessary that “two non anagrams can give the same product if overflow occurs during calculation of the product”. There are infinitely many products, so mapping them to a finite set (which would occur in the scenario with overflow) would result in different products getting mapped to the same code.

In my solution above I used the GMP library to avoid overflow, since there is no built-in type in C for arbitrarily sized integers.

6. matthew said

Well, this modification of my program, taking the encoding mod 232 doesn’t produce any false positives, but mod 228:

import sys
import functools
import operator
primes = [5,71,41,29,2,47,61,19,7,97,79,31,43,13,11,67,89,23,17,3,37,73,59,83,53,101]
def encode(s):
plist = (primes[ord(c)-ord('a')] for c in s)
return functools.reduce(operator.mul,plist,1) % 2**28
codes = {}
for line in sys.stdin:
word = line.rstrip()
if all("a" <= c <= "z" for c in word):
codes.setdefault(encode(word),[]).append(word)

for n in sorted(codes.keys()):
s = codes[n]
if len(s) >= 2:
for i in range(1,len(s)):
if sorted(s[0]) != sorted(s[i]): print(s[0],s[1])

finds the following non-anagrams:

harangued picker
chalkier dissecting
airfield instinctive

7. matthew said

Gah, that was meant to say “2^32” and “2^28” (I used the Python double asterisk though).

8. Daniel said

@Ernie, here’s an example where “two non anagrams can give the same product if overflow occurs during calculation of the product”.

Suppose that integers are 16-bit. For any string, if we append 16 of the same character, the one that maps to prime number 2, then the product after overflow would be 0.

For example, if we have strings “programming” and “praxis”, and the character “z” maps to prime number 2, then the following different strings would both have product 0 after overflow.

“programmingzzzzzzzzzzzzzzzz”

“praxiszzzzzzzzzzzzzzzz”

9. Daniel said

(“the following different strings” should say “the following non-anagrams”)

10. matthew said

In my solution, for 16-bit codes, all of ‘biochemical’, ‘flushes’, ‘grackle’, ‘mournfulness’, ‘pectorals’, ‘songsters’ and ‘supported’, none of which are anagrams of each other, have code 41950, along with ‘enlists’, ‘listens’, ‘silents’ and ‘tinsels’, which are indeed anagrams.

11. Ernie said

Using ulong arithmetic modulo 2^61 – 1 I get no false positives from the dictionary enable1.txt

12. […] task is to use prime numbers to recognize anagrams. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments […]