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

by

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!

More Related Contents:

  1. Fast way to tokenize a string in c
  2. The most efficient way to implement an integer based power function pow(int, int)
  3. What is the fastest substring search algorithm?
  4. Power by squaring for negative exponents
  5. Explain this snippet which finds the maximum of two integers without using if-else or any other comparison operator?
  6. How do you print the EXACT value of a floating point number?
  7. C – How to implement Set data structure?
  8. Print all the permutations of a string in C
  9. Gaussian elimination without result for acceleration
  10. signed and unsigned arithmetic implementation on x86
  11. Does C have any tools for doing string addition?
  12. Algorithm to pick values from array that sum closest to a target value?
  13. c search for target string in string [closed]
  14. Why this C code makes infinite loop?
  15. What’s the difference between “mod” and “remainder”?
  16. What integer hash function are good that accepts an integer hash key?
  17. Reading string from input with space character? [duplicate]
  18. Calculating factorial of large numbers in C
  19. Combine Gyroscope and Accelerometer Data
  20. C – Difference between “char var[]” and “char *var”?
  21. Why does strchr take an int for the char to be found?
  22. Append Char To String in C?
  23. Traverse Matrix in Diagonal strips
  24. Are floating point operations in C associative?
  25. How does strcmp() work?
  26. Why do strings in C need to be null terminated?
  27. Convert string to mathematical evaluation [closed]
  28. Inverting a 4×4 matrix
  29. Creating C formatted strings (not printing them)
  30. C split a char array into different variables

Leave a Comment