首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >查找两个数组元素的最大有效组合数

问查找两个数组元素的最大有效组合数
EN

Stack Overflow用户
提问于 2013-07-08 12:46:05
回答 2查看 1.4K关注 0票数 4

有两个n长数组( a和b )由整数> 2组成.

在每一个回合中,我都希望从每个数组( a[i]和b[j] )中删除一个整数,因为关于它们的某个条件是真的(例如,它们不是同质化的)。(如果条件不是真,我将尝试删除另一个组合)

毕竟,我想找到最大的旋转数,我可以做到这一点(直到没有可能的组合,以删除符合条件)。让我们称其为最佳的转弯数。

我试图用一个搜索算法和一个PriorityQueue来解决这个问题:

代码语言:javascript
复制
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的可能的余素组合数。这被用作两个数组的给定状态的成本。

代码语言:javascript
复制
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中删除了一个非辅素数组合。

代码语言:javascript
复制
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])]

问题是,对于大型整数数组,这种解决方案效率很低。所以我想知道这个问题是否有更好的解决办法。

示例:

代码语言:javascript
复制
n = 4
a = [2, 5, 6, 7] 
b = [4, 9, 10, 12]

可以删除:

代码语言:javascript
复制
(2, 4)
(5, 10)
(6, 9)

这将导致最佳解决方案:

代码语言:javascript
复制
a = [7]
b = [12]

但如果要移除:

代码语言:javascript
复制
(6, 12)
(2, 10)

我们就可以得到次优解:

代码语言:javascript
复制
a = [5, 7]
b = [4, 9]

该算法应该始终得到最佳的转弯数(在本例中为3)。

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-07-08 13:12:40

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

  • 构造二部图G,使得对于每一个Ai和Bj,如果GCD(Ai,Bj) >1时,G中有一个边(Ai,Bj)。
  • 求G的最大匹配
  • 匹配的基数是解决方案

我看不出怎么能更快地解决这个问题。

票数 3
EN

Stack Overflow用户

发布于 2013-07-09 15:36:33

我知道你把这个问题带到哪里去了。你解决这个问题是错误的,因为它的O(n^2)和贪婪。N <= 10^5.2> a,b< 10^9来自数组

我认为在这个问题上你必须找到一些窍门。在二部图中,所有的最大匹配算法都是TL算法。

票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17527009

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档