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:

    dissuaded strewn
    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 […]

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: