查找列表

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]]