查找數據集中元素之間關係的算法

Question

我有一個數據集，它由一組到另一組的關係組成。簡化的例子如下：

{A，B，C} - > {1，2，3}＃順序可以改變{2，1,3}也可以

{B，d} - > {2,4}

{A，d} - > {1,4}

---

我需要找到元素之間的關係，使得：

A - > 1

乙 - > 2

Ç - > 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_2 [j]之間的邊，使得S_1 [i] ∈ 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 

而如您建議的解決方案只是該圖中的最大匹配。