算法 - 如何有效地确保每个数组中的元素是不同的？

Question

我不知道如何写这个问题的标题.现有的标题可能不准确.

这是问题所在:

我有m组(数组),比方说,4组.每组包含一些数字.我们希望的是每个组给出一个数字,并且总共产生的4个数字(每个来自一个组)是不同的.

现在给出这4组,我怎样才能确保它们符合我们的愿望？

例如,

答:0,2,3

B:0,2

C:2,3

D:1

以上4组可以满足我们的愿望.D给出1,C给出3,B给出2,A给出0.

但如果

A2

B:2

C:2,3

D:1

很糟糕我们不能让每个小组给出一个明确的数字.

我的想法是最愚蠢的方式,我只是回溯所有组中的所有元素,以获得元素的每个组合,并从一个组合中看到这些元素是不同的.

谁有更好的主意？

Answer 1

您可以将此建模为网络流问题,然后在该问题域中使用快速算法(其中许多是多项式时间),如Edmunds-Karp或push-relabel.

创建源节点和汇聚节点.然后为每个"组"和每个不同的元素创建节点.将每个组节点连接到源,将每个元素节点连接到接收器.如果组作为元素,最后使用元素节点连接组节点.所有流量应为1.

用一个例子可以很好地说明这一点.我将使用您给出的第一个示例:

A: 0, 2, 3
B: 0, 2
C: 2, 3
D: 1

将变成以下流网络:

   A   0
  /     \
 /       \
S--B   1--T
 \       /|
  \     / |
   C   2 /
        /
       3

我无法绘制中间流.但是假设A流向0,2,3和B流向0,2,C流向2,3,D流向1.所有流量均为单位容量.

因此,首先在此图中找到最大流量.组和元素之间的流程将为您提供所需的二分匹配.

如果没有可能的匹配,则max-flow将小于组的数量.