python - 一个列表(可能)可以被另一个整除吗？

Question

问题

假设您有两个列表 A = [a_1, a_2, ..., a_n] 和 B = [b_1, b_2, ..., b_n]整数。如果存在 B 的排列使得 a_i对于所有 i， 可被 b_i 整除。那么问题是:是否可以重新排序(即置换) B 以便 a_i 对于所有 i< 都可以被 b_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 的所有排列，看看是否满足 potential-divisibility，类似于:

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 做到这一点，但我想不出一个解决方案。

非常感谢!

---

编辑:这可能与你们大多数人无关，但为了完整起见，我将解释我的动机。在群论中，有一个关于有限单群的猜想，即是否存在来自群的不可约特征和共轭类的双射，使得每个特征度都划分相应的类大小。例如，对于 U6(4) here are what A and B would look like.相当大的列表，请注意!

Answer 1

构建二分图结构 - 将 a[i] 与其所有来自 b[] 的除数连接起来。

然后找到maximum matching并检查它是否是完美匹配(匹配中的边数等于对数(如果图形是有向的)或双数)。

任意选择Kuhn algorithm implementation here .

更新:
@Eric Duminil 非常简洁 Python implementation here

这种方法的多项式复杂度从 O(n^2) 到 O(n^3)，具体取决于所选择的匹配算法和边数(除法对)与蛮力算法的阶乘复杂度。