如何将自枚举pangram表示为布尔函数？

Question

自我枚举pangrams的wiki文章指出它们是使用二元决策图计算的.我一直在阅读有关BDD的内容,根据我的理解,您需要先将一些问题表示为布尔函数,然后才能构建BDD.

我该怎么做呢？

我已经考虑了几天这个问题了,我很确定你可以使用简单的编码来表示布尔函数的输入:

10000 01010 01011 10101 ...
16A's 10B's 11C's 21D's ...

所以对于一个pangram开始"十六A,十B,十一C,二十一D",你可以把它表示为10000010100101110101 ......

这意味着布尔函数中有26*5 = 130个变量,假设您将字符的最大频率限制为32次出现.

输出应该是表示是否是自我枚举的pangram,即如果句子描述其自己的一组频率.

要做到这一点,在此过程中肯定需要一个哈希表(或几个).

因此,对于字母E,哈希表可能会开始:

one   -> 1
two   -> 0
three -> 2
four  -> 0
five  -> 1
...

二进制,可能看起来像:

1   -> 1
10  -> 0
11  -> 10
100 -> 0
101 -> 1

如果来自E哈希表的所有查找的总和等于对应于E的五个输入比特,那么自枚举庞格的那部分是正确的.如果所有部分都正确则布尔函数应该为1,否则为0.

我很确定我可以弄清楚如何使用布尔函数执行加法以及如何检查两个数字是否相等.但是,我不知道从何处开始将哈希表表示为布尔函数.此外,将所有部分连接在一起可能会让我感到困惑.

有什么想法吗？想法？合作？我想知道这是怎么回事.

提前致谢.

Answer 1

在我看来，在这种情况下使用 BDD 只是一种表示和协助操作用于评估的表达式的方式，例如，如果您的句子满足作为自枚举全语法的要求。有一些规则可以在概念上比布尔代数中的操作语句更容易地操作它们，因为它们用该表示法比用布尔表示法更容易表示，就像 8000 个变量的多项式更难处理一样其一般形式而不是代表其来源等的其他符号。计算机算法可用于操作这四种中的任何一种，因此您最好的选择可能是查找并根据您的需要调整一种算法。您可能会发现此文档很有帮助。

谷歌对于寻找其他资源也可能很有用。