在列表列表中查找最大重叠

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] 您 unify a 与 b 和 a 与 c。您对两个列表都执行此操作，然后导出结果根。

有一个简单的 disjunct-set 算法我们可以修改：

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:
        <b>if len(e) > 0:</b>
            <b>u = e[0]</b>
            if u not in mapping:
                mapping[u] = u
            <b>for v in e[1:]:</b>
                if v not in mapping:
                    mapping[v] = v
                mapping[parent(u,mapping)] = parent(v,mapping)
    return mapping

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

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

结果未排序，因为我们使用的是集合。不过，如果您愿意，可以通过将 f 更改为：

轻松地在每个元组的第一个元素上对其进行排序

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 <b>sorted(</b>[list(x) for x in results.values()]<b>,key=lambda t:t[0])</b>

产生：

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

这个解决方案的好处是，如果 a 或 b 本身有 overlap，它也可以工作，你可以很容易地概括使用任意数量列表的解决方案（例如 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]]

在列表列表中查找最大重叠

Find max overlap in list of lists

python

algorithm

list

overlap