查找可以完成元组的子集,无需重复

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 作为成本来表示可以做和不能做，并查看是否存在零成本答案。