模式匹配
假设我有一组像这样的元组（每个元组将有 1,2 或 3 个项目）：
主集：
{(A) (A,C) (B,C,E)}
假设我有另一组像这样的元组：
Real Set: {(BOB) (TOM) ( ERIC,SALLY,CHARLIE) (TOM,SALLY) (DANNY) (DANNY,TOM) (SALLY) (SALLY,TOM,ERIC) (BOB,SALLY) }
我想要做的是提取来自真实集的元组，其中元组成员可以被替换为与主集相同。
在上面的示例中，将返回两个集合：
{(BOB) (BOB,SALLY) (ERIC,SALLY,CHARLIE)}
(let BOB=A,ERIC=B,SALLY=C,CHARLIE=E)
和
{(DANNY) (DANNY,TOM) (SALLY,TOM,ERIC)}
(let DANNY=A,SALLY=B, TOM=C,ERIC=E)
它是一种模式匹配，我猜是一种组合学。我真的不知道如何对这个问题进行分类以及有哪些常见的攻击计划。 stackoverflow 专家会建议什么？
Suppose I have a set of tuples like this (each tuple will have 1,2 or 3 items):
Master Set:
{(A) (A,C) (B,C,E)}
and suppose I have another set of tuples like this:
Real Set: {(BOB) (TOM) (ERIC,SALLY,CHARLIE) (TOM,SALLY) (DANNY) (DANNY,TOM) (SALLY) (SALLY,TOM,ERIC) (BOB,SALLY) }
What I want to do is to extract all subsets of Tuples from the Real Set where the tuple members can be substituted to become the same as the Master Set.
In the example above, two sets would be returned:
{(BOB) (BOB,SALLY) (ERIC,SALLY,CHARLIE)}
(let BOB=A,ERIC=B,SALLY=C,CHARLIE=E)
and
{(DANNY) (DANNY,TOM) (SALLY,TOM,ERIC)}
(let DANNY=A,SALLY=B,TOM=C,ERIC=E)
Its sort of pattern matching, sort of combinatorics I guess. I really don't know how to classify this problem and what common plans of attack there are for it. What would the stackoverflow experts suggest?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
按大小将元组分成集合。在每个集合中，创建一个数据结构，使您能够有效地查询包含给定元素的元组。该结构的第一部分是将元组作为数组（以便每个元组都有一个规范索引）。第二组是：
Map String (Set Int)。这有点占用空间，但希望不是禁止的。然后，你本质上是暴力破解它。对于第一个主集的所有分配，将所有分配限制为其他主集。对于第二个的所有剩余分配，将所有分配限制为第三个及之后的分配，依此类推。该算法基本上是归纳的。
我应该补充一点，我不认为这个问题是 NP 完全的，而只是平坦的最坏情况指数。这不是一个决策问题，而是一个枚举问题。很容易想象输入呈指数级增长的场景。
Seperate your tuples into sets by size. Within each set, create a data structure that allows you to efficiently query for tuples containing a given element. The first part of this structure is your tuples as an array (so that each tuple has a cannonical index). The second set is:
Map String (Set Int). This is somewhat space intensive but hopefully not prohibative.Then, you, essentially, brute force it. For all assignments to the first master set, restrict all assignments to other master sets. For all remaining assignments to the second, restrict all assignments to the third and beyond, etc. The algorithm is basically inductive.
I should add that I don't think the problem is NP-complete so much as just flat worst-case exponential. It's not a decision problem, but an enumeration problem. And it's fairly easy to imagine scenarios of inputs that blow up exponentially.
由于您的问题可能是 NP 完全的（它包括子图同构作为特殊情况），因此很难有效地完成。不过，这是假设模式和数据库的大小各不相同。您要搜索多少数据？你的图案有多复杂？我会首先推荐暴力解决方案，然后测试它是否太慢并且您需要更高级的东西。
It will be difficult to do efficiently since your problem is probably NP-complete (it includes subgraph isomorphism as a special case). That assumes the patterns and database both vary in size, though. How much data are you searching? How complicated will your patterns be? I would recommend the brute force solution first, then test if that is too slow and you need something fancier.