有两个由大于 2 的整数组成的n 长度数组 (a和)。b
鉴于关于它们的某个条件为真（例如，它们不是互质数），我想在每一个回合中从每个数组（a[i]和）中删除一个整数。b[j]（如果条件不成立，我会尝试删除另一个组合）
毕竟我想找到我可以实现的最大圈数（直到没有可能的组合可以删除符合条件的组合）。让我们称之为最佳转数。
我尝试使用搜索算法和PriorityQueue使用 Python 来解决这个问题：
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）。