algorithm - 查找是否有任何集合被成员集合覆盖

Question

[如果这对应于一个已知问题，请告诉我]

我有 n 套不同尺寸的。集合中的每个元素都是唯一的。每个元素最多可以出现在两个不同的集合中。

我想对这些集合执行操作，但要避免重复或遗漏任何元素。问题:找出所有这 n 个集合中的哪些集合应该被删除，因为它们被其他集合覆盖了。

例如[a,b,c]; [A]; [b].删除 [a]、[b]，因为两者都被第一个覆盖。

例如[a,b,c]; [A]; [b]； [光盘]。删除 [a,b,c]，因为所有三个元素都被剩余集合覆盖。注意:此处 [a]、[b] 单独不是有效答案，因为 'c' 被重复。同样，[a]、[b]、[c,d] 不是有效答案，因为如果删除“d”，将会丢失。

Answer 1

我认为这是 Exact Cover problem .最后一个限制条件——每个元素最多属于两个集合——在我看来并没有从根本上改变问题(尽管我很容易在这一点上犯错)。维基百科网页包含对各种算法方法的很好的总结。选择的算法似乎是Dancing Links .