Возможный алгоритм определения того, являются ли две строки анаграммами друг друга?

Я написал быструю программу для поиска конфликтов методом грубой силы и обнаружил, что этот подход не всегда работает. Строки ABFN и AAHM имеют одинаковую сумму и произведение ASCII, но не являются анаграммами друг друга. Их сумма ASCII равна 279, а произведение ASCII равно 23 423 400.

Есть гораздо больше конфликтов, чем это. Моя программа, просматривая все строки длины четыре, нашла 11 737 конфликтов.

Для справки, вот исходный код C++:

#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];
        }
      }
    }
  }
}

Надеюсь это поможет!

Ваш подход неверен; Я не могу объяснить почему, потому что я этого не понимаю, но есть разные наборы, по крайней мере, для кардинальности 3, которые имеют одинаковую сумму и произведение: https://math.stackexchange.com/questions/38671/два-набора-из-3-положительных-целых-с-равной-суммой-и-произведением

Буквы a-z и A-Z используются для индексации массива из 26 простых чисел, а произведение этих простых чисел используется в качестве хеш-значения для слова. Равный продукт ‹--> одинаковые буквы.

(порядок хеш-значений в массиве primes26[] в приведенном ниже фрагменте основан на частоте букв в голландском языке, как попытка имитировать ожидаемый продукт)

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define COUNTOF(a) (sizeof (a)/ sizeof (a)[0])

typedef unsigned long long HashVal;
HashVal hashmem (char *str, size_t len);

unsigned char primes26[] =
{
5,71,79,19,2,83,31,43,11,53,37,23,41,3,13,73,101,17,29,7,59,47,61,97,89,67,
};

struct anahash {
        struct anahash *next;
        unsigned freq;
        HashVal hash;
        char word[1];
        };

struct anahash *hashtab[1024*1024] = {NULL,};
struct anahash *new_word(char *str, size_t len);
struct anahash **hash_find(struct anahash *wp);

/*********************************************/

HashVal hashmem (char *str, size_t len)
{
size_t idx;
HashVal val=1;

if (!len) return 0;
for (idx = 0; idx < len; idx++) {
        char ch = str[idx];
        if (ch >= 'A' && ch <= 'Z' ) val *= primes26[ ch - 'A'];
        else if (ch >= 'a' && ch <= 'z' ) val *= primes26[ ch - 'a'];
        else continue;
        }
return val;
}

struct anahash *new_word(char *str, size_t len)
{
struct anahash *wp;
if (!len) len = strlen(str);

wp = malloc(len + sizeof *wp );
wp->hash = hashmem(str, len);
wp->next = NULL;
wp->freq = 0;
memcpy (wp->word, str, len);
wp->word[len] = 0;
return wp;
}

struct anahash **hash_find(struct anahash *wp)
{
unsigned slot;
struct anahash **pp;

slot = wp->hash % COUNTOF(hashtab);

for (pp = &hashtab[slot]; *pp; pp= &(*pp)->next) {
        if ((*pp)->hash < wp->hash) continue;
        if (strcmp( wp->word, (*pp)->word ) > 0) continue;
        break;
        }
return pp;
}

char buff [16*4096];
int main (void)
{
size_t pos,end;
struct anahash *wp, **pp;
HashVal val;

memset(hashtab, 0, sizeof hashtab);

while (fgets(buff, sizeof buff, stdin)) {
        for (pos=0; pos < sizeof buff && buff[pos]; ) {
                for(end = pos; end < sizeof buff && buff[end]; end++ ) {
                        if (buff[end] < 'A' || buff[end] > 'z') break;
                        if (buff[end] > 'Z' && buff[end] < 'a') break;
                        }
                if (end > pos) {
                        wp = new_word(buff+pos, end-pos);
                        if (!wp) {pos=end; continue; }
                        pp = hash_find(wp);
                        if (!*pp) *pp = wp;
                        else if ((*pp)->hash == wp->hash
                         && !strcmp((*pp)->word , wp->word)) free(wp);
                        else { wp->next = *pp; *pp = wp; }
                        (*pp)->freq +=1;
                        }
                pos = end;
                for(end = pos; end < sizeof buff && buff[end]; end++ ) {
                        if (buff[end] >= 'A' && buff[end] <= 'Z') break;
                        if (buff[end] >= 'z' && buff[end] <= 'a') break;
                        }
                pos = end;
                }
        }
for (pos = 0;  pos < COUNTOF(hashtab); pos++) {
        if (! &hashtab[pos] ) continue;

        for (pp = &hashtab[pos]; wp = *pp; pp = &wp->next) {
                if (val != wp->hash) {
                        fprintf (stdout, "\nSlot:%u:\n", pos );
                        val = wp->hash;
                        }
                fprintf (stdout, "\t%llx:%u:%s\n", wp->hash, wp->freq, wp->word);
                }
        }

return 0;
}

Спасибо за такой отличный вопрос! Вместо того, чтобы пытаться полностью опровергнуть ваше предположение, я потратил некоторое время, пытаясь найти способы дополнить его, чтобы оно стало верным. У меня есть ощущение, что если стандартные отклонения равны, то они равны. Но вместо того, чтобы тестировать так далеко, я делаю более простой тест и пока не нашел контрпримера. Вот что я протестировал:

В дополнение к условиям, которые вы упомянули ранее,

• Квадратный корень ASCII из суммы квадратов должен быть равен:

Я использую следующую программу Python. У меня нет полных доказательств, но, возможно, мой ответ поможет. В любом случае, взгляните.

from math import sqrt

class Nothing:



def equalString( self, strA, strB ):
    prodA, prodB = 1, 1
    sumA, sumB = 0, 0
    geoA, geoB = 0, 0

    for a in strA:
      i = ord( a )
      prodA *= i
      sumA += i
      geoA += ( i ** 2 )
    geoA = sqrt( geoA )

    for b in strB:
      i = ord( b )
      prodB *= i
      sumB += i
      geoB += ( i ** 2 )
    geoB = sqrt( geoB )

    if prodA == prodB and sumA == sumB and geoA == geoB:
      return True
    else:
      return False


  def compareStrings( self ):
    first, last = ord( 'A' ), ord( 'z' )
    for a in range( first, last + 1 ):
      for b in range( a, last + 1 ):
        for c in range( b, last + 1 ):
          for d in range( c, last + 1 ):
            strA = chr( a ) + chr( b ) + chr( c ) + chr( d )
            strB = chr( d ) + chr( c ) + chr( b ) + chr( a )

            if not self.equalString( strA, strB ):
              print "%s and %s should be equal.\n" % ( strA, strB )

    print "Done"

Если вы не возражаете против изменения строк, отсортируйте каждую из них и сравните две подписи.