查找列表

Question

的名單最大重疊我列出的兩個列表：

a = [[0, 1, 5], [2], [3], [4], [6, 7], [8, 9, 10, 11], [12], [13], [14], [15]] 
b = [[0, 1], [2, 3], [4], [5], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

我怎樣才能找到列出的值之間的最大重疊，並建立列表的新列表，這個最大重疊。 換句話說，我正在尋找一個函數f，它通過合併具有重疊的列表來最大化列表大小。

的功能f這個例子的期望的結果將是：

f(a,b) = [[0, 1, 5], [2, 3], [4], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

Answer 1

可以使用disjoint-set structure的一個變體來解決這個問題：每個列表[a,b,c]你統一a與b和a與c。你爲這兩個列表做了這個，然後得出結果的根。

Here有一個簡單的間斷設置算法，我們可以修改：

from collections import defaultdict 

def parent(u,mapping): 
    if mapping[u] == u: 
     return u 
    mapping[u] = parent(mapping[u],mapping) 
    return mapping[u] 

def relation(array,mapping=None): 
    if mapping is None: 
     mapping = {} 

    for e in array: 
     if len(e) > 0: 
      u = e[0] 
      if u not in mapping: 
       mapping[u] = u 
      for v in e[1:]: 
       if v not in mapping: 
        mapping[v] = v 
       mapping[parent(u,mapping)] = parent(v,mapping) 
    return mapping 

def f(a,b): 
    mapping = {} 
    relation(a,mapping) 
    relation(b,mapping) 

    results = defaultdict(set) 
    for u in mapping.keys(): 
     results[parent(u,mapping)].add(u) 
    return [list(x) for x in results.values()]

（黑體字添加了與原來的工會設置算法語義差異）。

這將產生：

>>> f(a,b) 
[[2, 3], [4], [0, 1, 5], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

結果是沒有排序，因爲我們有一組工作。

def f(a,b): 
    mapping = {} 
    relation(a,mapping) 
    relation(b,mapping) 

    results = defaultdict(set) 
    for u in mapping.keys(): 
     results[parent(u,mapping)].add(u) 
    return sorted([list(x) for x in results.values()],key=lambda t:t[0])

產生：

>>> f(a,b) 
[[0, 1, 5], [2, 3], [4], [6, 7], [8, 9, 10, 11], [12], [13, 14], [15]] 

這種解決方案的好處是，它也可以不過，你可以很容易地通過改變f進行排序，如果你想每個元組的第一個元素如果存在重疊a或b本身，並且您可以輕鬆概括解決方案以使用任意數量的列表（例如a,b和c）。

Answer 2

當我的理解是正確的，下面將做：

[l for l in a if not any(all(x in l2 for x in l) for l2 in b)] + 
[l for l in b if not any(all(x in l2 for x in l) for l2 in a)] + 
[l for l in a if l in b] 

的第一項產生的a其不在b列出的部分全部名單;第二個術語產生b中的所有列表，如果在a列表中列出，則列出所有列表;第三項產生所有列表，這兩個列表均在a和b之間。

對於示例這會產生以下結果：

[[0, 1, 5], [2, 3], [13, 14], [4], [6, 7], [8, 9, 10, 11], [12], [15]]