寻找两个数组元素的最大有效组合数

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

< p > 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）。

- leezu

---

请包含函数 number_of_coprime_combinations 和 not_coprime_combinations 的代码。另外，请提供一组数据样本以及“结果”应该是什么。 - Inbar Rose

二分图最大匹配 - David Eisenstat

@DavidEisenstat 谢谢，我会告诉你是否有效。 - leezu

在HackerRank正在进行的比赛中的问题... - Jayram

Answer 1

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

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

• 找到G的最大匹配。

• 匹配的基数就是答案。

我不认为这可以更快地解决。

- svinja

---

谢谢，我需要了解这些图表。如果适用于我，我会告诉你的 ;)！ - leezu

Answer 2

我知道你遇到的问题所在。 然而，你提供的解决方案是错误的，因为它是O(n^2)和贪心算法。n <= 10^5，数组中的a、b满足2 > a，b < 10^9。

我认为，在这个问题中，你需要找到一些诀窍。所有用于二分图最大匹配的算法都会超时。

- Anonymmm

Answer 3

假设：

1. 函数 is_coprime_pair(pair) 已定义，接受一个长度为 2 的列表，并返回一对质数的 True
2. a 和 b 是可迭代对象，需要进行组合

    import itertools  
    not_coprimes = itertools.filterfalse(is_coprime_pair, itertools.product(a, b))

not_coprimes 将包含所有不包含两个质数的数对。

- ElmoVanKielmo

---

抱歉，问题有点不清楚。我尝试优化的不是 not_coprime_combinations 函数，而是整个算法 ;)
此外，not_coprime_combinations 应该返回一个状态列表，其中已删除数字的非互质组合。（状态是数组 a 和 b 的组合）。
例如：`>>> not_coprime_combinations([2,5,6],[4,9,10])` 应该返回 `[([5, 6], [9, 10]), ([5, 6], [4, 9]), ([2, 6], [4, 9]), ([2, 5], [9, 10]), ([2, 5], [4, 10]), ([2, 5], [4, 9])]` - leezu