在配對列表中查找配對的最大數量

Question

我有從特定數字生成的配對列表。我的問題並不涉及我的配對是如何計算的，因爲我已經計算出來了，但是最大化可能的配對總數。
例如：

[1,3,7,19,13,21] 

導致

{1:[19,13,21], 
3:[7,19], 
7:[3,19,13], 
19:[1,3,7,21], 
13:[1,7,21], 
21:[1,19,13]} 

1可與19，13對或21 3可以與7或19配對，等等。我的目標是最大限度地發揮獨特配對的作用，使我擁有最少的積分，而不需要配對。在這種情況下，可以有1-13，3-7和19-21，這樣可以保留0。但是你也可以做1-19,7-13，這會讓3和21沒有合作伙伴。

以前有沒有算法處理過這個問題？我考慮將它們放入圖表中，試圖找到最大的哈密爾頓路徑，但這看起來幾乎不可能。我在Python中這樣做，所以我有字典和列表，我一直使用容器。

編輯：一個數字是否可以配對的條件是它們是否與這一對形成了某種模式。給定兩個數字x和y，他們遵循這個模式，直到x == y或者它永遠消失。如果x < y， y = y - x和x = 2 * x。然後，它又來了，等...

Answer 1

，你描述的圖表找到maximal matching（在你的例子，如果i與j然後j還配備了i配對，讓您可以通過連接它們的問題一個邊緣）。以下python package以及 this code包含相關的實現。