Возможный алгоритм определения, являются ли две строки анаграммами друг друга?
У меня есть эта идея (с использованием языка C) для проверки, являются ли две строки, сформированные из букв ASCII, анаграммами друг друга:
Проверьте, имеют ли строки одинаковую длину.
Проверьте, является ли сумма значений ASCII всех символов одинаковой для обеих строк.
Проверьте, является ли произведение значений ASCII всех символов одинаковым для обеих строк.
Я считаю, что если все три верны, то строки должны быть анаграммами друг друга. Однако я не могу доказать это. Может ли кто-нибудь помочь мне доказать или опровергнуть, что это будет работать?
Спасибо!
5 ответов
Я написал быструю программу для поиска конфликтов методом грубой силы и обнаружил, что этот подход не всегда работает. Строки 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/two-sets- из-3-положительных целых чисел-с-равная суммы-и-продукта
Буквы az и AZ используются для индексации массива из 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"
Если вы не возражаете против изменения строк, отсортируйте каждую из них и сравните две подписи.