从一个随机的整数列表开始，比如说:
list = [2,5,7,1,3]
目标:最大限度地将列表中的每个条目与列表中的另一个条目配对。当且仅当 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](同样，除了上面的匹配约束之外)。我想象得到的流动网络的可视化将是水平对称的(即沿着源-汇轴，因此是标题)。
我知道如何使用 MaxFlow 解决二分匹配问题，但不知道如何实现最后一个粗体约束。任何帮助都会非常，呃，有帮助。
最佳答案
附加约束(如果 A[m] 匹配 B[n] 那么 A[n] 也必须匹配 B [m]) 从根本上改变了问题的性质。事实上，该约束破坏了输入图的二分性，实际上将其变成了一般的无向图。因此，您正在寻找的是一种在一般图中找到最大匹配的算法。
问题可以用Edmonds Algorithm解决它展示了与二部案例的最大流量解决方案不同的方法(尽管它确实使用了增广路径的概念)。该算法利用了二分匹配可以很容易解决的事实，并且在某种程度上尝试通过折叠奇数循环将输入图变成二分(当且仅当它没有奇数循环时，图是二分的，因此数图中的奇数循环测量输入图远非二分图的程度)。上面的链接详细解释了该算法的工作原理。
这是 a Python implementation of the algorithm .该算法对于稀疏图相当有效，但对于密集图不是很有效。图的密度取决于有多少对条目 m, n 满足条件 (m + n)/gcd(m, n) 是 2 的幂。如果大多数对满足条件，运行时间将约为 O(n^4)。一般来说，运行时间是 O(E•V^2)。
关于python - 列表中元素的对称二分匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42794263/