列表(可能)可以被另一个整除吗？
McG*_*ire 67 python algorithm primes numbers division
问题
假设您有两个列表A = [a_1, a_2, ..., a_n]和B = [b_1, b_2, ..., b_n]整数.我们说A是潜在的,可分割的B,如果有一个置换B,使得a_i整除b_i所有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)
题
知道列表是否可能被另一个列表整除的最快方法是什么？有什么想法吗？我在想是否有一种聪明的方法可以用素数做到这一点,但我无法想出一个解决方案.
非常感激!
编辑:这可能与大多数人无关,但为了完整起见,我会解释我的动机.在群论中,有一个关于有限单群的猜想是关于是否存在来自群组的不可约的字符和共轭类的双射,使得每个字符度除以相应的类大小.例如,对于U6(4) 这里是什么A和B会是什么样子.相当大的名单,请注意!
Eri*_*nil 30
码
基于@ 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-Karp算法,该算法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
以下是相应的图表:
Tim*_*ers 17
由于你对数学很满意,我只想为其他答案添加光泽.要搜索的术语以粗体显示.
问题是具有受限制位置的排列的实例,并且可以说有很多关于那些的排列.通常,可以构造零一NxN矩阵M,其中M[i][j]当且仅当j原始位置处的元素的位置允许时为1 i.的数目满足所有的限制不同的排列是,则永久的M(限定的相同的方式决定因素,不同之处在于所有术语非负).
唉 - 与决定因素不同 - 没有已知的通用方法来计算永久性比指数式更快N.然而,存在用于确定永久物是否为0的多项式时间算法.
而这正是你得到的答案开始 ;-)这里有一个好交代如何"是永久的0？" 通过考虑二分图中的完美匹配来有效地回答问题:
https://cstheory.stackexchange.com/questions/32885/matrix-permanent-is-0
所以,在实践中,你不太可能找到比@Eric Duminil在答案中给出的更快的一般方法.
注意,稍后补充:我应该让最后一部分更清楚.给定任何"限制置换"矩阵M,很容易构造对应于它的整数"可分配列表".因此,您的具体问题并不比一般问题容易 - 除非可能有一些特殊的关于哪些整数可能出现在您的列表中.
例如,假设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].等等.通过施工,
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.