python - 查找两个数组元素的最大有效组合数

Question

有两个长度为 n 的数组(a 和 b)，由大于 2 的整数组成。

每次我都想从每个数组(a[i] 和 b[j])中删除一个整数，前提是关于它们的特定条件为真(例如，它们不是互质的)。 (如果条件不成立，我将尝试删除另一个组合)

毕竟我想找到我可以实现的最大圈数(直到没有可能的组合可以删除满足条件的)。我们称其为最佳圈数。

我尝试通过搜索算法和使用 Python 的 PriorityQueue 来解决这个问题:

def search(n, a, b):
    q = queue.PriorityQueue()
    encountered = set()
    encountered.add((tuple(a), tuple(b)))
    q.put((number_of_coprime_combinations(a, b), a, b))

    while q:
        cost, a, b = q.get()
        combs = not_coprime_combinations(a, b)

        if not combs:
            return n - len(a)

        for a, b in combs:
            if not (tuple(a), tuple(b)) in encountered:
                q.put((number_of_coprime_combinations(a, b), a, b))
                encountered.add((tuple(a), tuple(b)))

number_of_coprime_combinations(a, b) 返回给定数组 a 和 b 的可能互素数组合的数量。这用作两个数组的给定状态的成本。

def number_of_coprime_combinations(a, b):
    n = 0

    for idx_a, x in enumerate(a):
        for idx_b, y in enumerate(b):
            if is_coprime(x, y):
                n += 1

    return n

not_coprime_combinations(a, b) 返回可能状态的列表，其中非互质组合已从 a 和 b:

def not_coprime_combinations(a, b):
    l = []

    for idx_a, x in enumerate(a):
        for idx_b, y in enumerate(b):
            if not is_coprime(x, y):
                u, v = a[:], b[:]
                del(u[idx_a])
                del(v[idx_b])
                l.append((u, v))

    return l

>>> not_coprime_combinations([2,3],[5,6])
[([3], [5]), ([2], [5])]

问题是这个解决方案对于大整数数组来说效率非常低。所以我想知道是否有更好的解决方案来解决这个问题..

示例:

n = 4
a = [2, 5, 6, 7] 
b = [4, 9, 10, 12]

可以删除:

(2, 4)
(5, 10)
(6, 9)

这将导致最佳解决方案:

a = [7]
b = [12]

但是如果有人要删除:

(6, 12)
(2, 10)

一个人会得到次优的解决方案:

a = [5, 7]
b = [4, 9]

算法应始终得出最佳转数(在本例中为 3)。

Answer 1

据我所知，要解决这个问题:

• 构造二分图 G，使得对于每个 Ai 和 Bj，如果 GCD(Ai,Bj) > 1，则 G 中存在一条边 (Ai, Bj)。

• 找到G的最大匹配

• 匹配的基数就是解决方案

我不知道如何更快地解决这个问题。