有两个长度为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)。
number_of_coprime_combinations
和not_coprime_combinations
的代码。另外,请提供一组数据样本以及“结果”应该是什么。 - Inbar Rose