算法符合人們基於多種可能的匹配

Question

比方說，我有一組5人P = {1, 2, 3, 4, 5}的，我知道有它們匹配在一起的下列可能性：

{1,2}, {1,3}, {1,5}, {2,1}, {2,4}, {2,5}, {3,1}, {3,4}, {4,2}, {4,3}, {4,5}, {5,1}, {5,2}, {5,4} 

例如，它們可以象徵誰喜歡誰（每個人都是雙性戀， 性別無所謂）。

顯現爲圖：

現在我想其實知道是誰相互匹配，使每個人都與別人相匹配。理想情況下，沒有人被排除在外。

那麼基於這個例子：誰應該與誰結婚？理想情況下，沒有人應該保持單身。

有點扭曲：也可以最多3人匹配在一起。

所以基於這個例子：允許多婚姻婚姻。

所以我可以手動做到這一點，並得到一個有效的結果。所以我知道，因爲{1,2}，{1,5}和{2,5}我可以匹配{1,2,5}在一起。

現在這意味着人1,2和5都出去了，只留下了以下組合：

{3,4}, {4,3} 

導致{3,4}。

所以最終的結果可能是：{1,2,5}和{3,4}

所以基礎上，例如：人1，2和5結婚的人3 和5結婚。

再者，可視化爲曲線圖：現在

，這是一個玩具的例子。如果人數和可能的比賽數量增加，情況會變得更加複雜。

我正在尋找如何解決這個計算機問題的正確方向。

Answer 1

你可以像

# people is a frozenset 
# conflicts is a set of frozenset pairs 
def match(people, conflicts): 
    if not people: # people is empty 
     return {} 
    for group in next_groups(people, conflicts): 
     solution = match(people - group, conflicts) 
     if solution is not None: 
      solution.add(group) 
      return solution 
    return None 


def next_groups(people, conflicts): 
    a = min(people) 
    for b in people - {a}: 
     if frozenset({a, b}) in conflicts: 
      continue 
     yield frozenset({a, b}) 
     for c in people - {a, b}: 
      if frozenset({a, c}) in conflicts or frozenset({b, c}) in conflicts: 
       continue 
      yield frozenset({a, b, c}) 

一個有些殘酷的遞歸Python函數和memoize的它（查找people在字典，看看有什麼輸出是最後一次）。