查找兩個陣列

有兩個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

查找兩個陣列

回答

相關問題