判断一组集合是否可以 “cover”范围的算法

Question

假设您有一组有限且任意的集合，并且每个内部集合都可以包含从 1 到 4 的不重复的整数。所以一个集合可以是 {{1}, {1,4}, {1,4}, {1,2,3,4,4}, {2,3,4}}。假设您有一个要求，即您有一组必须位于内部集合中的数字，但内部集合只能为该要求贡献一个数字。

这可能令人困惑，所以让我举个例子:假设需求是 {1,2,3,4} 并且集合是 {{1,2, 3, 4}, {3,4}, {1,2}, {1,2}}。它满足要求，因为你可以从第一个内部集合中取出 3 个，从第二个中取出 4 个，从第三个中取出 1 个，从最后一个中取出 2 个。但是，如果集合是 {{1,2,3,4}, {1,2}, {1,2}, {1,2}} 那么这不符合要求，因为您可能会得到 3 或 4从第一个内部集合，但不能从任何其他内部集合中得到另一个。

请注意，对于要求，重复是可以的:因此允许 {1,1,3} 的要求。

所以我的问题是:给定一个要求和一个集合，您将如何编写算法来确定该集合是否满足条件？

感谢阅读本文!

Answer 1

取内集的叉积，看看它是否包含要求。 (这里所说的集合 A 和 B 的叉积，我指的是可以通过从 A 中取一个元素和从 B 中取一个元素来导出的所有集合；如果正好有一个元素是一个集合，则将另一个元素添加到该集合中；如果两者都是是集合，取他们的并集。)