在配对列表中查找配对的最大数量

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包含相关的实现。