functional-programming - 模式匹配

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) }
我想要做的是从真实集中提取元组的所有子集，其中元组成员可以替换为与主集相同。

在上面的例子中，将返回两个集合:

{(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)

它是某种模式匹配，我猜是某种组合。我真的不知道如何对这个问题进行分类以及针对它有哪些常见的攻击计划。 stackoverflow 专家会建议什么？

Answer 1

按大小将元组分成多个集合。在每个集合中，创建一个数据结构，允许您有效地查询包含给定元素的元组。这个结构的第一部分是你的元组作为一个数组(这样每个元组都有一个规范的索引)。第二组是:Map String (Set Int) .这有点占用空间，但希望不是禁止性的。

然后，你，基本上，蛮力它。对于第一个主集的所有分配，将所有分配限制到其他主集。对于第二个的所有剩余分配，将所有分配限制为第三个及以后，依此类推。该算法基本上是归纳法。

我应该补充一点，我不认为问题是 NP 完全的，而只是平坦的最坏情况指数。这不是决策问题，而是枚举问题。很容易想象输入呈指数级增长的场景。