Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

A possible algorithm for determining whether two strings are anagrams of one another? [closed]

I have this idea (using C language) for checking whether two strings formed from ASCII letters are anagrams of one another:

  1. Check if the strings are the same length.

  2. Check if the sum of the ASCII values of all chars is the same for both strings.

  3. Check if the product of the ASCII values of all chars is the same for both strings.

I believe that if all three are correct, then the strings must be anagrams of one another. However, I can't prove it. Can someone help me prove or disprove that this would work?

Thanks!

like image 418
Alex Goltser Avatar asked Feb 06 '13 21:02

Alex Goltser


People also ask

What is anagram algorithm?

The anagram algorithm is a simple algorithm. Create a function where you compare two strings and check if they are anagrams of each other. The strings can contain any type of characters like “Hi, there!” and “There… hI!

How do you know if two words are anagrams?

Two words are anagrams of each other if they contain the same number of characters and the same characters. You should only need to sort the characters in lexicographic order, and determine if all the characters in one string are equal to and in the same order as all of the characters in the other string.


2 Answers

I wrote a quick program to brute-force search for conflicts and found that this approach does not always work. The strings ABFN and AAHM have the same ASCII sum and product, but are not anagrams of one another. Their ASCII sum is 279 and ASCII product is 23,423,400.

There are a lot more conflicts than this. My program, searching over all length-four strings, found 11,737 conflicts.

For reference, here's the C++ source code:

#include <iostream>
#include <map>
#include <string>
#include <vector>
using namespace std;

int main() {
  /* Sparse 2D table where used[sum][prod] is either nothing or is a string
   * whose characters sum to "sum" and whose product is "prod".
   */
  map<int, map<int, string> > used;

  /* List of all usable characters in the string. */
  vector<char> usable;
  for (char ch = 'A'; ch <= 'Z'; ch++) {
    usable.push_back(ch);
  }
  for (char ch = 'a'; ch <= 'z'; ch++) {
    usable.push_back(ch);
  }

  /* Brute-force search over all possible length-four strings.  To avoid
   * iterating over anagrams, the search only explores strings whose letters
   * are in increasing ASCII order.
   */
  for (int a = 0; a < usable.size(); a++) {
    for (int b = a; b < usable.size(); b++) {
      for (int c = b; c < usable.size(); c++) {
        for (int d = c; d < usable.size(); d++) {
          /* Compute the sum and product. */
          int sum  = usable[a] + usable[b] + usable[c] + usable[d];
          int prod = usable[a] * usable[b] * usable[c] * usable[d];

          /* See if we have already seen this. */
          if (used.count(sum) &&
              used[sum].count(prod)) {
            cout << "Conflict found: " << usable[a] << usable[b] << usable[c] << usable[d] << " conflicts with " << used[sum][prod] << endl;
          }

          /* Update the table. */
          used[sum][prod] = string() + usable[a] + usable[b] + usable[c] + usable[d];
        }
      }
    }
  }
}

Hope this helps!

like image 115
templatetypedef Avatar answered Sep 29 '22 18:09

templatetypedef


Your approach is false; I can't explain why because I don't understand it, but there are different sets at least for cardinality 3 that have the same sum and product: https://math.stackexchange.com/questions/38671/two-sets-of-3-positive-integers-with-equal-sum-and-product

like image 21
G. Bach Avatar answered Sep 29 '22 17:09

G. Bach