algorithm - 在对列表中找到最大数量的对

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