列表中元素的对称二分匹配
Symmetric Bipartite Matching of Elements in List
从一个随机的整数列表开始，比如：
list = [2,5,7,1,3]
Objective：最大程度地将列表中的每个条目与列表中的另一个条目配对。当且仅当 log_base_2((m + n) / gcd(m, n)) 不是整数时，可以匹配值 (m,n) 的条目。 IE。 (7,3) 是有效匹配，而 (1,3) 不是。
我很确定执行此操作的一种方法是生成两个列表 A 和 B，相当于初始列表：
A=B=list=[2,5,7,1,3]
然后将其视为二分匹配问题，附加约束条件是如果 A[m] 匹配 B[n]，则 A[n] 也必须匹配 B[m]（同样，除了上面的匹配约束）。我想象得到的流动网络的可视化将是水平对称的（即沿着 source-sink 轴，因此标题）。
我知道如何使用 MaxFlow 解决二分匹配问题，但不知道如何实现最后一个加粗的约束。任何帮助都会非常，呃，有帮助。
附加约束（如果 A[m] 匹配 B[n]，则 A[n] 也必须匹配 B[m]）从根本上改变了问题的性质。事实上，该约束破坏了输入图的二分性，实际上将其变成了一般的无向图。因此，您正在寻找的是一种在一般图中找到最大匹配的算法。
这个问题可以使用 Edmonds Algorithm 来解决，它展示了与二部情况的最大流解决方案不同的方法（尽管它确实使用了增广路径的概念）。该算法利用了二分匹配可以很容易解决的事实，并且在某种程度上尝试通过折叠奇数循环将输入图变成二分（当且仅当它没有奇数循环时，图是二分的，因此数图中的奇数循环测量输入图远非二分图的程度）。上述 link 中详细解释了该算法的具体工作原理。
这是a Python implementation of the algorithm。该算法对于稀疏图相当有效，但对于密集图不是很有效。图的密度取决于有多少对条目 m, n 满足条件 (m + n) / gcd(m, n) 是 2 的幂。如果大多数对满足条件，则运行时间约为 O(n^4)。一般来说，运行时间是 O(E•V^2).
事实证明这根本不是二分匹配问题 - 相反，它是 "Non-Bipartite Maximum Matching." 的更一般的 class Edmonds/'Blossom' algorithm provides the solution ()。
经过一番搜索，我发现了 Edmonds/'Blossom' 算法的一个简单实现，我最终使用了该算法：
http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/
它利用了 Guido Van Rossum 非常直观的图形结构：
https://www.python.org/doc/essays/graphs/
祝未来的读者好运！
从一个随机的整数列表开始，比如：
list = [2,5,7,1,3]
Objective：最大程度地将列表中的每个条目与列表中的另一个条目配对。当且仅当 log_base_2((m + n) / gcd(m, n)) 不是整数时，可以匹配值 (m,n) 的条目。 IE。 (7,3) 是有效匹配，而 (1,3) 不是。
我很确定执行此操作的一种方法是生成两个列表 A 和 B，相当于初始列表：
A=B=list=[2,5,7,1,3]
然后将其视为二分匹配问题，附加约束条件是如果 A[m] 匹配 B[n]，则 A[n] 也必须匹配 B[m]（同样，除了上面的匹配约束）。我想象得到的流动网络的可视化将是水平对称的（即沿着 source-sink 轴，因此标题）。
我知道如何使用 MaxFlow 解决二分匹配问题，但不知道如何实现最后一个加粗的约束。任何帮助都会非常，呃，有帮助。
附加约束（如果 A[m] 匹配 B[n]，则 A[n] 也必须匹配 B[m]）从根本上改变了问题的性质。事实上，该约束破坏了输入图的二分性，实际上将其变成了一般的无向图。因此，您正在寻找的是一种在一般图中找到最大匹配的算法。
这个问题可以使用 Edmonds Algorithm 来解决，它展示了与二部情况的最大流解决方案不同的方法（尽管它确实使用了增广路径的概念）。该算法利用了二分匹配可以很容易解决的事实，并且在某种程度上尝试通过折叠奇数循环将输入图变成二分（当且仅当它没有奇数循环时，图是二分的，因此数图中的奇数循环测量输入图远非二分图的程度）。上述 link 中详细解释了该算法的具体工作原理。
这是a Python implementation of the algorithm。该算法对于稀疏图相当有效，但对于密集图不是很有效。图的密度取决于有多少对条目 m, n 满足条件 (m + n) / gcd(m, n) 是 2 的幂。如果大多数对满足条件，则运行时间约为 O(n^4)。一般来说，运行时间是 O(E•V^2).
事实证明这根本不是二分匹配问题 - 相反，它是 "Non-Bipartite Maximum Matching." 的更一般的 class Edmonds/'Blossom' algorithm provides the solution (
经过一番搜索，我发现了 Edmonds/'Blossom' 算法的一个简单实现，我最终使用了该算法： http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/
它利用了 Guido Van Rossum 非常直观的图形结构： https://www.python.org/doc/essays/graphs/
祝未来的读者好运！