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

Question

我有一个数据集，其中包含从一个集合到另一个集合的关系。简化示例如下:

{A, B, C} -> {1, 2, 3} # order may change {2, 1, 3} 也是可能的

{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, S_2[j]∈ s'_2 和 s'_1，则在 S_1[i] 和 S_2[j] 之间添加边 → 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

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