如何完全匹配一组集合

Question

此问题类似于 "Exact Hitting Set" 问题 (http://en.wikipedia.org/wiki/Exact_cover#Exact_hitting_set)，但约束条件略有不同。

我正在寻找解决以下问题的库、实现或论文。

假设我有一组集合S，初始化如下：

S = {N, O, P, E};

N = {1, 2, 5}
O = {4, 5}
P = {1, 6, 7}
E = {2, 3, 8}};

S有n个集合，每个子集合的大小未知。在这个例子中 n = 4

现在我有另一个大小为 n 的集合 X，它被初始化为：

X = {1, 2, 4, 6}

我需要做的是将 X 中的每个元素与 S.[=15= 中的一个且仅一个集合匹配]

所以 S 应该完全满足映射到 X 的所有集合，反之亦然。

X[0] --> N
X[1] --> E
X[2] --> O
X[3] --> P

我遇到的主要问题是如何处理 S 集合中的重复数据。我该如何处理这些碰撞？以及如何以相对可扩展的方式实现算法？

如果您有任何信息可以为我指明解决此问题的正确方向，我们将不胜感激。

Answer 1

您可以通过以下方式创建二分图：

然后有了二分图，您可以使用 hopcroft karp algorithm 产生最大基数匹配来解决问题。(O(|E|sqrt(V)))

How to match a set against a set of sets, completely