在对列表中找到最大数量的对
Find the maximum amount of pairs in a list of pairs
我有一个从某些数字生成的对列表。我的问题与如何计算我的配对无关，因为我已经弄明白了，而是最大化可能的配对总数。
例如：
[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。然后又开始了，等等...
您描述的问题是找到 maximal matching in a graph (in your example, if i is paired with j then j is also paired with i, so you can connect them by an edge). The following python package 以及
this code 包含相关实现。
我有一个从某些数字生成的对列表。我的问题与如何计算我的配对无关，因为我已经弄明白了，而是最大化可能的配对总数。
例如：
[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。然后又开始了，等等...
您描述的问题是找到 maximal matching in a graph (in your example, if i is paired with j then j is also paired with i, so you can connect them by an edge). The following python package 以及
this code 包含相关实现。