在一个列表的列表中找到最大重叠

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

- elcombato

---

你自己试过吗？ - Chris_Rands

如果说a包含[1,2],[3,4]，而b包含[2,3]，那么结果是否应该包含[1,2,3,4]？ - Willem Van Onsem

如果@WillemVanOnsem在评论中提到的案例是真实的，那么为什么[6, 7], [8, 9, 10, 11]没有作为[6, 7, 8, 9, 10, 11]出现在所需的输出中？ - Moinuddin Quadri

由于没有“桥”（[7, 8]），我就这样假设了。 - Ma0

因为没有一个列表包含这两个列表的元素。只有在存在一个包含这两个列表实例的列表时，它们才会被合并。 - Willem Van Onsem

Answer 1

你可以使用 不相交集合 的变体来解决这个问题：对于每个列表 [a,b,c]，你需要将 a 与 b 和 a 与 c 进行合并。你需要对两个列表都进行此操作，然后得到结果的根。 这里 有一个简单的不相交集合算法，我们可以进行修改。

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本身存在重叠，它也能正常工作，并且您可以轻松地将该解决方案推广到任意数量的列表（例如a，b和c）。

- Willem Van Onsem

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

- phynfo

---

这并不总是会生成传递闭包。比如你有 a = [[1,2],[3,4],[5,6]] 和 b = [[2,3],[4,5]]，结果是 [[1, 2], [3, 4], [5, 6], [2, 3], [4, 5]]，而期望的结果是 [[1,2,3,4,5,6]]... - Willem Van Onsem