我有这个想法（使用 C 语言）来检查由 ASCII 字母组成的两个字符串是否是彼此的字谜：
检查字符串的长度是否相同。
检查两个字符串的所有字符的 ASCII 值的总和是否相同。
检查两个字符串的所有字符的 ASCII 值的乘积是否相同。
我相信如果这三个都是正确的，那么这些字符串必须是彼此的字谜。但是，我无法证明。有人可以帮我证明或反驳这行得通吗？
谢谢！
问问题
6079 次
5 回答
11
我写了一个快速程序来蛮力搜索冲突，发现这种方法并不总是有效。字符串 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];
}
}
}
}
}
希望这可以帮助！
于 2013-02-06T21:52:09.067 回答
5
你的方法是错误的；我无法解释为什么，因为我不明白，但至少对于基数 3 有不同的集合，它们具有相同的总和和乘积：https ://math.stackexchange.com/questions/38671/two-sets- of-3-positive-integers-with-equal-sum-and-product
于 2013-02-06T21:50:38.610 回答
5
字母 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;
}
于 2013-02-06T22:17:21.293 回答
4
谢谢你提出这么好的问题！我没有试图完全反驳你的主张，而是花了一些时间试图找到方法来增强它，使它成为真的。我的感觉是，如果标准差相等，则两者相等。但是，我没有进行那么远的测试，而是进行了更简单的测试，并且还没有找到反例。这是我测试过的：
除了你之前提到的条件，
- 平方和的 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"
于 2013-02-07T00:44:30.513 回答
1
如果您不介意修改字符串，请对每个字符串进行排序并比较两个签名。
于 2013-02-06T22:08:19.160 回答