查找成员集是否涵盖任何集合

Question

[如果这映射到已知问题,请告诉我]

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

我想对这些集合执行操作,但避免重复或丢失任何元素.问题:找出应删除所有这些n集的内容,因为它们被其他集覆盖.

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

例如[a,b,c]; [一个]; 并[b]; [光盘].删除[a,b,c],因为所有三个元素都被剩余的集合覆盖.注意:此处[a],[b]单独无效答案,因为'c'正在重复.类似地,[a],[b],[c,d]无效答案,因为如果删除则会遗漏'd'.

Answer 1

我认为这就是精确覆盖问题。最后一个约束——每个元素最多位于两个集合中——在我看来并没有从根本上改变问题（尽管我很容易在这一点上犯错）。维基百科网页包含对各种算法方法的很好的总结。选择的算法似乎是Dancing Links。