模式匹配

Question

假设我有一组这样的元组(每个元组将有1,2或3项)：

主集合：

 {(A) (A,C) (B,C,E)}

假设我有另一组元组，如下所示：

实集：{(BOB) (TOM) (ERIC,SALLY,CHARLIE) (TOM,SALLY) (DANNY) (DANNY,TOM) (SALLY) (SALLY,TOM,ERIC) (BOB,SALLY) }

我想要做的是从Real中提取所有元组子集，其中元组成员可以被替换成与主集合相同。

在上面的示例中，将返回两组：

{(BOB) (BOB,SALLY) (ERIC,SALLY,CHARLIE)}

(让BOB=A，ERIC=B，SALLY=C，CHARLIE=E)

和

{(DANNY) (DANNY,TOM) (SALLY,TOM,ERIC)}

(让DANNY=A，SALLY=B，TOM=C，ERIC=E)

它是一种模式匹配，某种组合，我猜。我真的不知道如何分类这个问题，也不知道有什么共同的攻击计划。堆积如山的专家会提出什么建议？

Answer 1

按大小将您的元组分成几组。在每个集合中，创建一个数据结构，使您能够有效地查询包含给定元素的元组。这个结构的第一部分是作为数组的元组(因此每个元组都有一个规范索引)。第二组是：Map String (Set Int)。这在一定程度上是空间密集，但希望不是抑制性的。

那么，从本质上说，你是蛮力的。对于第一个主集的所有分配，限制所有分配到其他主集。对于所有剩余的分配到第二次，限制所有的分配到第三次及以后，等等。

我应该补充一点，我认为问题不在于NP-完全，而仅仅是平坦的最坏情况指数。这不是一个决策问题，而是一个枚举问题。我们很容易想象投入指数爆炸的情景。

Answer 2

由于您的问题可能是NP-完全的(它包括子图同构作为特例)，所以很难有效地完成。不过，这假设模式和数据库的大小都不一样。你在搜索多少数据？你的模式会有多复杂？我会首先推荐蛮力的解决方案，然后测试它是否太慢，你需要更漂亮的东西。