アルゴリズム

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} 

例えば、彼らが象徴する可能性が誰が誰を好きですか（誰もがバイセクシャルです、 性別は関係ありません）。グラフとして可視

：

今私は実際には誰もが誰かと一致するように、相互に一致させるために誰かを知りたいです。理想的には誰も出ていません。

例に基づいて：誰と誰と結婚するべきですか？理想的には誰も1人でいられないはずです。

少しねじれ：また、最大3人を一緒に照合することもできます。

したがって、この例に基づいて、多彩な結婚が許可されます。

私はそれを手動で行い、結果を得ることができます。だから私は{1,2}のため、{1,5}と{2,5}私は{1,2,5}を合わせることができることを知っている。 {3,4}につながる

{3,4}, {4,3} 

を：

は、今では人の1,2及び5のみ次の組み合わせを残している、出ていることを意味しています。

最終的な結果は、可能性が{1,2,5}及び{3,4}

だから例に基づいて：人1、2及び5が結婚した人3 得ます5人は結婚する。

再び、グラフとして視覚化：

さて、これはおもちゃの一例です。人と可能性のある試合の数が増えれば、はるかに複雑になります。

私はコンピュータでこのような問題を解決する方法について正しい方向にプッシュを探しています。

Answer 1

あなたは（出力が最後の時間だったかを見るために辞書でpeopleを調べる）

# 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することができます。