关于自我枚举pangram的wiki文章指出,它们是使用二进制决策图计算的。我一直在读有关BDD的文章,根据我的理解,在为它构造BDD之前,您需要将一些问题表示为布尔函数。
我该怎么做呢?
我已经考虑这个问题好几天了,我确信你可以用一种简单的编码来表示布尔函数的输入:
10000 01010 01011 10101 ...
16A's 10B's 11C's 21D's ...
因此,对于一个以“16个A,10个B,11个C,21个D”开头的pangram,你可以将其表示为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的五个输入位,则自枚举pangram的该部分是正确的。如果所有部分都正确,则布尔函数应生成1,否则为0。
我很确定我可以弄清楚如何使用布尔函数进行加法,以及如何检查两个数字是否相等。但是,我不知道从哪里开始将哈希表表示为布尔函数。此外,将所有这些部分连接在一起可能会让我感到困惑。
有什么想法吗?想法?协作?我想看看这是怎么回事。
提前谢谢。
发布于 2012-09-15 05:22:28
在我看来,BDDs的使用,就像在这个上下文中使用的那样,只是表示和帮助操作用于计算的表达式的一种方式,例如,如果您的句子满足自枚举pangram的要求。有一些规则可以用来操作它们,这些规则在概念上比那些在布尔代数中操作语句的规则更容易,因为它们在该符号中比在布尔符号中更容易表示,就像8000个变量的多项式在其一般形式下比在其他表示它来自何处的符号中更难处理一样。计算机算法可以操作这四种算法中的任何一种,所以您最好的选择可能是查找并根据您的需要调整其中一种。您可能会发现this document很有帮助。
在查找其他资源时,Google可能也很有用。
https://stackoverflow.com/questions/12290221
复制相似问题