一个列表（可能）可以被另一个整除吗？
Is a list (potentially) divisible by another?
问题
假设您有两个整数列表 A = [a_1, a_2, ..., a_n] 和 B = [b_1, b_2, ..., b_n]。我们说 A 可以被 B 整除 如果存在 B 的排列使得 a_i 可以被 [=19 整除=] 所有 i。那么问题是：是否可以重新排序（即置换）B，以便 a_i 可以被 b_i 整除所有 i？
例如，如果您有
A = [6, 12, 8]
B = [3, 4, 6]
那么答案将是 True，因为 B 可以重新排序为 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)
问题
知道一个列表是否可以被另一个列表整除的最快方法是什么？有什么想法吗？我在想是否有一种聪明的方法可以用 primes 来做到这一点，但我想不出一个解决方案。
非常感谢！
编辑：这可能与你们大多数人无关，但为了完整起见，我将解释我的动机。群论中有一个关于有限单群的猜想，是否存在来自群的不可约特征和共轭classes的双射使得每个特征度都划分相应的class大小。例如，对于 U6(4) here are what A and B would look like. 非常大的列表，请注意！
构建二分图结构 - 将 a[i] 与其来自 b[] 的所有除数连接起来。
然后找到maximum matching并检查它是否完美匹配（匹配的边数等于对数（如果图是有向的）或倍数）。
任意选择Kuhn algorithm implementation here。
更新：
@Eric Duminil 非常简洁
此方法具有从 O(n^2) 到 O(n^3) 的多项式复杂度，具体取决于所选的匹配算法和边数（除法对）相对于蛮力算法的阶乘复杂度。
你可以试试这个：
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
这不是最终答案，但我认为这可能是有价值的。您可以先列出列表[(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)]中所有元素的因数（包括1和自身）。我们正在寻找的列表必须具有其中一个因素（平均分配）。
由于我们在列表中没有某些因素，我们正在检查 ([2,7,5,3,12,3]) 此列表可以进一步过滤为：
[(2,5),(2,3,12),(2,3),(5),(3,7),(5)]
在这里，有两个地方需要 5（我们根本没有任何选择），但我们只有 5，所以，我们几乎可以在这里停下来，说这里的情况是错误的。
假设我们有 [2,7,5,3,5,3] 而不是：
那么我们会有这样的选择：
[(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被取了，所以3的两个位置是可以保证的：
[{2},{3},{3},{5},(3,7),{5}]现在当然拿了3个，保证了7个：
[{2},{3},{3},{5},{7},{5}]。这仍然与我们的列表一致，因此案例是真实的。请记住，我们将在我们可以轻松突破的每次迭代中查看与列表的一致性。
代码
以@MBo 的优秀 , here's an implementation of bipartite graph matching using 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
备注
根据 documentation:
The dictionary returned by maximum_matching() includes a mapping for
vertices in both the left and right vertex sets.
表示返回的dict应该是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-Karp algorithm，最坏情况下运行在O(n**2.5)。图的生成是O(n**2)，所以整个方法的运行时间是O(n**2.5)。它应该适用于大型阵列。排列解决方案是 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
对应的图表如下：
既然你对数学很满意，我只想为其他答案增光添彩。 粗体.
中显示要搜索的字词
问题是位置受限的排列的一个实例，关于这些可以说的很多。通常，当且仅当位置 j 允许最初位于位置 [=17] 的元素时，可以构造零一 NxN 矩阵 M，其中 M[i][j] 为 1 =].满足所有限制的 number 个不同的排列就是 M 的 permanent （定义方式与行列式相同，除了所有项都是非负的）。
唉 - 与行列式不同 - 在 N 中没有比指数更快的已知通用方法来计算永久值。但是，有多项式时间算法可以确定永久是否为0。
这就是你得到答案的地方 start ;-) 这里很好地说明了如何通过考虑二分图中的完美匹配来有效地回答 "is the permanent 0?" 问题：
https://cstheory.stackexchange.com/questions/32885/matrix-permanent-is-0
因此，在实践中，您不太可能找到比@Eric Duminil 在他们的回答中给出的方法更快的通用方法。
注意，稍后添加：我应该使最后一部分更清楚。给定任何"restricted permutation"矩阵M，很容易构造出与之对应的整数"divisibilty lists"。因此，您的特定问题并不比一般问题更容易 - 除非您的列表中可能出现哪些整数有特殊之处。
例如，假设M是
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
查看表示前 4 个质数的行，它们也是 B:
中的值
B = [2, 3, 5, 7]
第一行然后"says"那B[0] (= 2)不能除A[0]，必须除A[1]，A[2]，A[3] ].等等。通过构建，
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.
的相应元素整除
问题
假设您有两个整数列表 A = [a_1, a_2, ..., a_n] 和 B = [b_1, b_2, ..., b_n]。我们说 A 可以被 B 整除 如果存在 B 的排列使得 a_i 可以被 [=19 整除=] 所有 i。那么问题是：是否可以重新排序（即置换）B，以便 a_i 可以被 b_i 整除所有 i？
例如，如果您有
A = [6, 12, 8]
B = [3, 4, 6]
那么答案将是 True，因为 B 可以重新排序为 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)
问题
知道一个列表是否可以被另一个列表整除的最快方法是什么？有什么想法吗？我在想是否有一种聪明的方法可以用 primes 来做到这一点，但我想不出一个解决方案。
非常感谢！
编辑：这可能与你们大多数人无关，但为了完整起见，我将解释我的动机。群论中有一个关于有限单群的猜想，是否存在来自群的不可约特征和共轭classes的双射使得每个特征度都划分相应的class大小。例如，对于 U6(4) here are what A and B would look like. 非常大的列表，请注意！
构建二分图结构 - 将 a[i] 与其来自 b[] 的所有除数连接起来。
然后找到maximum matching并检查它是否完美匹配（匹配的边数等于对数（如果图是有向的）或倍数）。
任意选择Kuhn algorithm implementation here。
更新：
@Eric Duminil 非常简洁
此方法具有从 O(n^2) 到 O(n^3) 的多项式复杂度，具体取决于所选的匹配算法和边数（除法对）相对于蛮力算法的阶乘复杂度。
你可以试试这个：
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
这不是最终答案，但我认为这可能是有价值的。您可以先列出列表[(1,2,5,10),(1,2,3,6,12),(1,2,3,6),(1,5),(1,3,7,21),(1,5,25)]中所有元素的因数（包括1和自身）。我们正在寻找的列表必须具有其中一个因素（平均分配）。
由于我们在列表中没有某些因素，我们正在检查 ([2,7,5,3,12,3]) 此列表可以进一步过滤为：
[(2,5),(2,3,12),(2,3),(5),(3,7),(5)]
在这里，有两个地方需要 5（我们根本没有任何选择），但我们只有 5，所以，我们几乎可以在这里停下来，说这里的情况是错误的。
假设我们有 [2,7,5,3,5,3] 而不是：
那么我们会有这样的选择：
[(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被取了，所以3的两个位置是可以保证的：
[{2},{3},{3},{5},(3,7),{5}]现在当然拿了3个，保证了7个：
[{2},{3},{3},{5},{7},{5}]。这仍然与我们的列表一致，因此案例是真实的。请记住，我们将在我们可以轻松突破的每次迭代中查看与列表的一致性。
代码
以@MBo 的优秀
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
备注
根据 documentation:
The dictionary returned by maximum_matching() includes a mapping for vertices in both the left and right vertex sets.
表示返回的dict应该是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-Karp algorithm，最坏情况下运行在O(n**2.5)。图的生成是O(n**2)，所以整个方法的运行时间是O(n**2.5)。它应该适用于大型阵列。排列解决方案是 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
对应的图表如下：
既然你对数学很满意，我只想为其他答案增光添彩。 粗体.
中显示要搜索的字词问题是位置受限的排列的一个实例，关于这些可以说的很多。通常，当且仅当位置 j 允许最初位于位置 [=17] 的元素时，可以构造零一 NxN 矩阵 M，其中 M[i][j] 为 1 =].满足所有限制的 number 个不同的排列就是 M 的 permanent （定义方式与行列式相同，除了所有项都是非负的）。
唉 - 与行列式不同 - 在 N 中没有比指数更快的已知通用方法来计算永久值。但是，有多项式时间算法可以确定永久是否为0。
这就是你得到答案的地方 start ;-) 这里很好地说明了如何通过考虑二分图中的完美匹配来有效地回答 "is the permanent 0?" 问题：
https://cstheory.stackexchange.com/questions/32885/matrix-permanent-is-0
因此，在实践中，您不太可能找到比@Eric Duminil 在他们的回答中给出的方法更快的通用方法。
注意，稍后添加：我应该使最后一部分更清楚。给定任何"restricted permutation"矩阵M，很容易构造出与之对应的整数"divisibilty lists"。因此，您的特定问题并不比一般问题更容易 - 除非您的列表中可能出现哪些整数有特殊之处。
例如，假设M是
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
查看表示前 4 个质数的行，它们也是 B:
B = [2, 3, 5, 7]
第一行然后"says"那B[0] (= 2)不能除A[0]，必须除A[1]，A[2]，A[3] ].等等。通过构建，
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.