查找可以补全为无重复元组的子集

Question

我们有一组 A_1,...,A_n 的集合。目标是为每个旧集合找到新集合。

newA_i = {a_i in A_i such that there exist (a_1,..,a_n) in (A1,..,An) with no a_k = a_j for all k and j}

因此，用语言来说，这表示我们从 A_i 中删除所有不能用于从集合 (A_1,..,A_n) 中形成元组 (a_1,..a_n) 的元素，使得该元组不包含重复项。

我的问题是如何快速计算这些新集合。如果您只是通过生成所有可能的 v 来实现此定义，这将需要指数时间。你知道更好的算法吗？

编辑：这是一个例子。现在

A_1 = {1,2,3,4}
A_2 = {2}. 

，新集合如下所示：

newA_1 = {1,3,4}
newA_2 = {2}

2 已从 A_1 中删除，因为如果您选择它，则元组将始终为 (2,2)，这是无效的，因为它包含重复项。另一方面，1,3,4 是有效的，因为 (1,2)、(3,2) 和 (4,2) 是有效的元组。

另一个例子：

A_1 = {1,2,3}
A_2 = {1,4,5}
A_3 = {2,4,5}
A_4 = {1,2,3}
A_5 = {1,2,3}

现在新的集合是：

newA_1 = {1,2,3}
newA_2 = {4,5}
newA_3 = {4,5}
newA_4 = {1,2,3}
newA_5 = {1,2,3}

1 和 2 从集合 2 和 3 中删除，因为如果您从这些集合中选择 1 或 2，您将只剩下 2 个值用于集合 1、4 和 5，所以您将元组中始终存在类似于 (_,1,_,_,_) 或 (_,_,2,_,_) 的重复项。

这个问题看起来很难，但是如果有一个多项式时间的算法就太好了。

另一种看待此问题的方法是，将集合 A_i 绘制在左侧，将值绘制在右侧，如果该值在集合中，则用一条线连接集合和值。

Answer 1

我认为分配算法在这里可能会有所帮助。基本步骤是固定 Ai 中的一个数字，然后看看该数字是否可以与从 Aj 中选择的其他数字一起使用，从每组中选择一个数字而不重复。将数字视为人，将集合 Aj 中的数字视为可能用于执行任务 j 的人。那么从每个Aj中找到不同的代表的问题就是为每个任务分配不同的人的问题。

维基百科将分配问题视为所有可能的分配以及每个分配的成本 http://en.wikipedia.org /wiki/Assignment_problem。在我们的例子中，我们可以使用 0 和 1 作为成本来表示可以做和不能做，并查看是否存在零成本答案。

Answer 2

我仍在考虑如何解决这个问题，但我决定尝试重写这个问题，看看它是否给我任何启发。

给定一组 N 组：

A_i = {a_i0, a_i1, ..., a_ij, ...}

找到

B_i such that x is in B_i if and only if:
   x is in A_i and
   there exists {c_0, c_1, c_2, c_3, ..., c_N} such that
      c_i = x and
      c_k is in A_k for all k and
      c_k != c_l for all k != l