列表（可能）被另一个整除吗？
问题
假设你有两个列表A = [a_1, a_2, ..., a_n]和B = [b_1, b_2, ..., b_n]的整数。 我们说如果B有一个排列使得a_i可以被b_i 整除 ，那么A就可以被B整除。 那么问题是：是否有可能重sorting（即置换） B使得a_i可以被b_i整除所有i ？ 例如，如果你有
A = [6, 12, 8] B = [3, 4, 6]
那么答案会是True ，因为B可以被重新sorting为B = [3, 6, 4] a_3 / b_3 = 2 B = [3, 6, 4] ，然后我们将有a_1 / b_1 = 2 ， a_2 / b_2 = 2和a_3 / b_3 = 2 ，所有这是整数，所以A可能被B整除。
作为一个应该输出False的例子，我们可以有：
A = [10, 12, 6, 5, 21, 25] B = [2, 7, 5, 3, 12, 3]
这是False的原因是我们不能重新排列B因为25和5在A ，但是B唯一的除数是5，所以一个会被排除。
途径
显而易见，直接的方法是获得B所有排列，看看是否能满足潜在的可分性 ，如下：
import itertools def is_potentially_divisible(A, B): perms = itertools.permutations(B) divisible = lambda ls: all( x % y == 0 for x, y in zip(A, ls)) return any(divisible(perm) for perm in perms)
题
什么是最快的方式知道一个列表是否可能被另一个列表整除？ 有什么想法吗？ 我在想，是否有一个聪明的方式来做这个素数 ，但我不能拿出一个解决scheme。
非常感激！
编辑 ：这可能与大多数人无关，但为了完整性，我会解释我的动机。 在群论中，有限简单群的猜想是关于是否存在来自群的不可约特征和共轭类的双射，使得每个特征等级划分相应的类大小。 例如，对于U6（4）， 这里是A和B样子。 漂亮的大名单，介意你！
构build二分图结构 – 将a[i]与b[]所有除数连接起来。 
然后find最大匹配，并检查它是否完美匹配 （ 匹配中的边数等于对的数量（如果图被定向）或者加倍的数）。
这里任意selectKuhnalgorithm实现 。
UPD：
@Eric Duminil在这里做了非常简洁的Python实现
这种方法从O（n ^ 2）到O（n ^ 3）具有多项式复杂度，取决于所select的匹配algorithm以及蛮力algorithm的阶数（边对）与阶乘复杂度。
码
基于@ MBo的优秀答案 ，下面是使用networkx实现双向图匹配。
import networkx as nx def is_potentially_divisible(multiples, divisors): if len(multiples) != len(divisors): return False g = nx.Graph() g.add_nodes_from([('A', a, i) for i, a in enumerate(multiples)], bipartite=0) g.add_nodes_from([('B', b, j) for j, b in enumerate(divisors)], bipartite=1) edges = [(('A', a, i), ('B', b, j)) for i, a in enumerate(multiples) for j, b in enumerate(divisors) if a % b == 0] g.add_edges_from(edges) m = nx.bipartite.maximum_matching(g) return len(m) // 2 == len(multiples) print(is_potentially_divisible([6, 12, 8], [3, 4, 6])) # True print(is_potentially_divisible([6, 12, 8], [3, 4, 3])) # True print(is_potentially_divisible([10, 12, 6, 5, 21, 25], [2, 7, 5, 3, 12, 3])) # False
笔记
根据文件 ：
maximum_matching（）返回的字典包含左右顶点集合中顶点的映射。
这意味着返回的字典应该是A和B两倍大。
节点被转换
[10, 12, 6, 5, 21, 25]
至：
[('A', 10, 0), ('A', 12, 1), ('A', 6, 2), ('A', 5, 3), ('A', 21, 4), ('A', 25, 5)]
以避免A和B节点之间的冲突。 该id还被添加以便在重复的情况下保持节点不同。
效率
maximum_matching方法使用Hopcroft-Karpalgorithm ，最坏情况下运行在O(n**2.5)中。 图的生成是O(n**2) ，所以整个方法运行在O(n**2.5) 。 它应该适合大数组。 排列解决scheme是O(n!) ，不能处理20个元素的数组。
用图表
如果您对显示最佳匹配的图感兴趣，可以混合使用matplotlib和networkx：
import networkx as nx import matplotlib.pyplot as plt def is_potentially_divisible(multiples, divisors): if len(multiples) != len(divisors): return False g = nx.Graph() l = [('l', a, i) for i, a in enumerate(multiples)] r = [('r', b, j) for j, b in enumerate(divisors)] g.add_nodes_from(l, bipartite=0) g.add_nodes_from(r, bipartite=1) edges = [(a,b) for a in l for b in r if a[1] % b[1]== 0] g.add_edges_from(edges) pos = {} pos.update((node, (1, index)) for index, node in enumerate(l)) pos.update((node, (2, index)) for index, node in enumerate(r)) m = nx.bipartite.maximum_matching(g) colors = ['blue' if m.get(a) == b else 'gray' for a,b in edges] nx.draw_networkx(g, pos=pos, arrows=False, labels = {n:n[1] for n in g.nodes()}, edge_color=colors) plt.axis('off') plt.show() return len(m) // 2 == len(multiples) print(is_potentially_divisible([6, 12, 8], [3, 4, 6])) # True print(is_potentially_divisible([6, 12, 8], [3, 4, 3])) # True print(is_potentially_divisible([10, 12, 6, 5, 21, 25], [2, 7, 5, 3, 12, 3])) # False
这里是相应的图表：
既然你对math感到满意，我只想给其他答案添加一些光泽。 以粗体显示要search的术语。
这个问题是一个有限位的排列实例，关于这些问题还有很多可以说的。 一般来说，当且仅当位置j原来在位置i的元素被允许时， M[i][j]为1的情况下可以构造一个零1的NxNmatrixM 满足所有限制的不同排列的数量就是M的永久性 （除了所有的项都是非负数外，其定义与行列式相同）。
唉 – 与行列式不同 – 没有已知的一般方法来计算永久性快于N指数。 但是，有多项式时间algorithm用于确定永久性是否为0。
这就是你得到的答案开始 ;-)这是一个很好的说明如何“是永久的0？ 通过在二部图中考虑完美匹配，问题得到有效解答：
https://cstheory.stackexchange.com/questions/32885/matrix-permanent-is-0
所以，在实际操作中，你不可能比任何一个@Eric Duminil的答案都快。
请注意，稍后添加：我应该使最后一部分更清楚。 给定任何“限制置换”matrixM ，很容易构造与之对应的整数“可分性列表”。 因此，您的具体问题并不比普通问题简单 – 除非您的列表中可能出现哪些整数可能有些特殊之处。
例如，假设M是
0 1 1 1 1 0 1 1 1 1 0 1 1 1 1 0
查看行代表前4个素数，这也是B的值：
B = [2, 3, 5, 7]
第一行然后“说” B[0] (= 2)不能分A[0] ，但必须除A[1] ， A[2]和A[3] 。 等等。 通过build设，
A = [3*5*7, 2*5*7, 2*3*7, 2*3*5] B = [2, 3, 5, 7]
对应于M 并且有permanent(M) = 9方法来排列B ，使得A每个元素都可以被排列的B的相应元素整除。
这不是最终的答案，但我认为这可能是值得的。 您可以首先列出列表中所有元素[(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)] 。 我们正在寻找的名单必须有其中的一个因素（均匀划分）。 由于我们在列表中没有一些因素，我们正在检查（ [2,7,5,3,12,3] ）。这个列表可以被进一步过滤为：
[(2,5),(2,3,12),(2,3),(5),(3,7),(5)]
在这里，需要5个地方（我们根本没有任何select），但是我们只有5个地方，所以我们可以在这里停下来说这里的情况是错误的。
假设我们有[2,7,5,3,5,3] ：
那么我们可以有这样的select：
[(2,5),(2,3),(2,3),(5),(3,7),(5)]
由于需要5个地方在两个地方：
[(2),(2,3),(2,3),{5},(3,7),{5}]其中{}表示确定的位置。
另外2确保：
[{2},(2,3),(2,3),{5},(3,7),{5}]既然2被拿走了，
[{2},{3},{3},{5},(3,7),{5}]当然有3个，
[{2},{3},{3},{5},{7},{5}] 。 这仍然与我们的名单一致，所以casse是真实的。 请记住，我们将在每一次我们可以随时爆发的迭代中查看我们列表的一致性。
你可以试试这个：
import itertools def potentially_divisible(A, B): A = itertools.permutations(A, len(A)) return len([i for i in A if all(c%d == 0 for c, d in zip(i, B))]) > 0 l1 = [6, 12, 8] l2 = [3, 4, 6] print(potentially_divisible(l1, l2))
输出：
True
另一个例子：
l1 = [10, 12, 6, 5, 21, 25] l2 = [2, 7, 5, 3, 12, 3] print(potentially_divisible(l1, l2))
输出：
False
