binary - 如何将自枚举 pangram 表示为 bool 函数？

Question

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

我该怎么做呢？

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

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

因此，对于以“16 个 A、10 个 B、11 个 C、21 个 D”开头的全字符组，您可以将其表示为 10000010100101110101...

这意味着 bool 函数中有 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 的五个输入位，则自枚举 pangram 的该部分是正确的。如果所有部分都正确，则 bool 函数应产生 1，否则为 0。

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

有什么想法吗？想法？合作？我想看看这是怎么回事。

提前致谢。

Answer 1

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

Google也可能有助于寻找其他资源。