查找数据集中元素之间关系的算法

Question

我有一个数据集，其中包含一组与另一组之间的关系。简化示例如下：

{A, B, C} -> {1, 2, 3} # order may change {2, 1, 3} is also possible

{B, D} -> {2, 4}

{A, D} -> {1, 4}

---

我需要找到元素之间的关系：

A -> 1

B -> 2

C -> 3

D -> 4

是否有针对此类任务的已知算法？

Answer 1

您可以在二部图中使用最大匹配来模拟这一点。制作两组顶点，例如一个包含顶点：S_1 = {A,B,C,D}，另一个包含元素 S_2 = {1,2,3,4}.

如果存在集合 s'_1,s'_2 使得 S_1[i] ∈ 在 S_1[i] 和 S_2[j] 之间添加边； s'_1, S_2[j]∈ s'_2 和 s'_1 右箭头; s'_2。然后使用一种众所周知的算法（例如匈牙利算法）在相应的二分图中找到最大匹配。

例如在你的例子中我们有边：

A,1
A,2
A,3
A,4
B,1
B,2
B,3
B,4
C,1
C,2
C,3
D,2
D,4

例如您建议的解决方案只是该图中的最大匹配。