查找两个阵列

有两个n长度阵列（a和b）由整数> 2.查找两个阵列

在每一个的元素转我想从每个阵列中移除的整数有效组合的最大数量（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）。

来源

2013-07-08 leezu

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

[双图中的最大配对]（https://en.wikipedia.org/wiki/Matching_（graph_theory）#Maximum_matchings_in_bipartite_graphs） –

@InbarRose fixed;） – leezu

据我所知，为了解决这样的：

构建二分图G，使得对于每个艾和Bj，如果GCD（艾，BJ）> 1，有一个在G.边缘（艾，BJ）
查找最大匹配ģ
的
匹配的基数是溶液

我看不出如何更快地解决这个问题。

来源

2013-07-08 13:12:40 svinja

thx，我必须阅读这些图。如果它适合我，我会告诉你;）！ – leezu

假设：

功能is_coprime_pair(pair)被定义，接受长度为2的列表并返回True 用于一对素数
a和b是iterables的结合

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

not_coprimes将容纳所有不含有的对两个素数

来源

2013-07-08 13:10:35 ElmoVanKielmo

Sry，这个问题有点不清楚。这不是'not_coprime_combinations'函数我试图优化，但整个alogrithm;）此外，not_coprime_combinations应该返回一个状态列表，其中一个非 - coprime数字组合已被删除。（状态是数组'a'和'b'的组合）。例如： '>>> not_coprime_combinations（[2,5,6]，[4,9,10]）'should return '[（[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

我知道你采取了这个问题。而你解决这个问题是错误的，因为它的O（n^2）和贪婪。 n < = 10^5。 2> a，b < 10^9 from array

我想在这个问题中你必须找到一些把戏。并且在二部图中最大匹配的所有算法都将是TL。

来源

2013-07-09 15:36:33 Anonymmm

查找两个阵列

回答

相关问题