R 包含组合生成
R Constained Combination generation
假设我有一组字符串：
x=c("a1","b2","c3","d4")
如果我有一套必须满足的规则：
- 如果"a1"和"b2"在一组，那么"c3"不能在那个组。
- 如果"d4"和"a1"在一个组中，那么"b2"不能在那个组中。
我想知道什么样的高效算法适合生成满足这些规则的所有组合？有什么研究或论文或任何东西谈论这些类型的约束组合生成问题？
在上述问题中，假设其combn(x,3)
我对 R 一无所知，所以我将只解决这个问题的理论方面。
首先，约束实际上是 "a1 ^ b2 -> ¬c3" 等形式的布尔谓词。这意味着所有有效组合都可以由一个 binary decision diagram 表示，可以通过获取每个约束并将它们组合在一起来创建。从理论上讲，您可能会以这种方式制作指数级大的 BDD（这通常不会发生，但取决于问题的结构），但这意味着您无论如何都无法真正列出所有组合，所以它可能还不错.
例如，为这两个约束生成的 BDD 将是（我认为 - 未测试 - 只是为了提供一个想法）
但由于这实际上是关于集合的，所以 ZDD 可能效果更好。 BDD 和 ZDD 之间的大致区别在于 BDD 压缩具有相等子树的节点（在所有可能性的总树中），而 ZDD 压缩实边节点（即 "set this variable to 1"）去假。两者都重复使用相同的子树，从而形成一个 DAG。
示例的 ZDD 将是（再次未测试）
我发现 ZDD 在代码中更容易操作一些，因为只要可以设置变量，它就会出现在 ZDD 中。相反，在 BDD 中，必须检测 "skipped" 个节点，包括 "between the last node and the leaf"，因此对于 BDD，您必须跟踪您的宇宙。对于 ZDD，大多数操作都独立于全域（补码除外，在集合族场景中很少需要）。缺点是在构造约束时必须了解宇宙，因为它们必须包含约束中未提及的所有变量的 "don't care" 路径。
您可以在计算机编程艺术第 4A 卷第 7.1.4 章中找到有关 BDD 和 ZDD 的更多信息，有一个免费的旧版本 here。
这些方法特别适合表示大量此类组合，并在生成所有可能性之前以某种方式操纵它们。因此，当有很多项目和很多约束（这样组合的最终计数不会太大）时，这也将起作用，（通常）不会创建指数大小的中间结果。
假设我有一组字符串：
x=c("a1","b2","c3","d4")
如果我有一套必须满足的规则：
- 如果"a1"和"b2"在一组，那么"c3"不能在那个组。
- 如果"d4"和"a1"在一个组中，那么"b2"不能在那个组中。
我想知道什么样的高效算法适合生成满足这些规则的所有组合？有什么研究或论文或任何东西谈论这些类型的约束组合生成问题？
在上述问题中，假设其combn(x,3)
我对 R 一无所知，所以我将只解决这个问题的理论方面。
首先，约束实际上是 "a1 ^ b2 -> ¬c3" 等形式的布尔谓词。这意味着所有有效组合都可以由一个 binary decision diagram 表示，可以通过获取每个约束并将它们组合在一起来创建。从理论上讲，您可能会以这种方式制作指数级大的 BDD（这通常不会发生，但取决于问题的结构），但这意味着您无论如何都无法真正列出所有组合，所以它可能还不错.
例如，为这两个约束生成的 BDD 将是（我认为 - 未测试 - 只是为了提供一个想法）
但由于这实际上是关于集合的，所以 ZDD 可能效果更好。 BDD 和 ZDD 之间的大致区别在于 BDD 压缩具有相等子树的节点（在所有可能性的总树中），而 ZDD 压缩实边节点（即 "set this variable to 1"）去假。两者都重复使用相同的子树，从而形成一个 DAG。
示例的 ZDD 将是（再次未测试）
我发现 ZDD 在代码中更容易操作一些，因为只要可以设置变量，它就会出现在 ZDD 中。相反，在 BDD 中，必须检测 "skipped" 个节点，包括 "between the last node and the leaf"，因此对于 BDD，您必须跟踪您的宇宙。对于 ZDD，大多数操作都独立于全域（补码除外，在集合族场景中很少需要）。缺点是在构造约束时必须了解宇宙，因为它们必须包含约束中未提及的所有变量的 "don't care" 路径。
您可以在计算机编程艺术第 4A 卷第 7.1.4 章中找到有关 BDD 和 ZDD 的更多信息，有一个免费的旧版本 here。
这些方法特别适合表示大量此类组合，并在生成所有可能性之前以某种方式操纵它们。因此，当有很多项目和很多约束（这样组合的最终计数不会太大）时，这也将起作用，（通常）不会创建指数大小的中间结果。