2

我试图找到几个选定答案的答案，但它们似乎不起作用。我必须合并列表列表。

[[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]

例如，我想要的只是[283,311]存在于[311,283,316]. 那么两者都应该合并，只在上面的列表中列出一个列表。如果列表存在于其他列表中，我需要合并它。

请注意，我可以使用循环内循环来做到这一点，但正在寻找一种pythonic方式来实现这一点。此外，如果您知道如何合并共享至少一个共同元素的列表，请分享。

编辑 ：

请不要忘记，寻找pythonic方法。我认为不可能使用任何核心 Pythonic 方法。那么使用循环的下一个可能的解决方案应该是什么。我需要效率，因为必须每半小时合并超过一百万个项目的列表列表。我确实在 for 循环中使用了 for 循环，然后比较了两个项目，但这花费了太多时间。

4

3 回答 3

8

回答你的后一个问题；这是一个连接组件问题。

>>> import networkx as nx
>>> G = nx.Graph()
>>> for component in l:
...:     G.add_edges_from(pairs(component))
...:     
>>> nx.connected_components(G)
# the answer
于 2013-04-19T14:29:21.993 回答
3

如果您有大量小集合，我认为这是一种替代方法，它应该比@mgilson 更快：

from collections import defaultdict

sets = set(map(frozenset, lists))

def remove_subsets(sets):
    # map each element to the sets in which it occurs
    sets_containing = defaultdict(set)
    for s in sets:
        for x in s:
            sets_containing[x].add(s)

    for s in sets:
        supersets = set.intersection(*(sets_containing[x] for x in s))
        if len(supersets) == 1:
            yield s

不同之处主要在于最后一个循环，它不是通过所有 n(n-1)/2 个不同的集合对，而是只通过外循环中的n 个集合，然后通过一组包含某些元素的候选超集正在考虑的集合。它可以通过reduce在产生空集时停止早期来进一步优化。

于 2013-04-19T14:58:57.130 回答
3

我认为这行得通...

a = [[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]
aa = set(map(frozenset,a))  #eliminate duplicates
result =  [x for x in aa if not any(x < y for y in aa)]

请注意，这会为您提供frozenset对象列表，但您可以轻松地将其转换回列表列表：

result = [list(fset) for fset in result]

不幸的是，它具有二次复杂性......我不确定是否真的有什么要做的......（将其保留为列表会导致更糟糕的复杂性 FWIW）

这是第二种方法，在算法上要好一些：

from itertools import takewhile
def foo2(aa):
    aa = sorted(set(map(frozenset,a)),key=len)
    def conditional(x,aa):
        xlen = len(x)
        return any(x < y for y in takewhile(lambda z: xlen <= len(z),aa))
    return [x for x in aa if not conditional(x,aa)]

当然，它需要对你的真实数据进行计时，看看它是否真的表现得更好（对于测试数据，列表不够大，生成conditional函数和takewhile实例的开销lambda使得它不值得。

出于好奇，这是我的基准：

a = [[283, 311], [311, 283, 316], [150, 68], [86, 119], [259, 263], [263, 259, 267], [118, 87], [262, 264], [264, 262], [85, 115], [115, 85], [244, 89], [140, 76, 82, 99], [236, 111], [330, 168], [76, 63, 107, 124, 128, 135, 140], [131, 254], [254, 131], [21, 38], [38, 21], [220, 291], [291, 220], [296, 46], [64, 53, 57, 61, 63, 65, 66, 76, 96, 100, 103, 114, 123, 127, 128, 130, 148, 149], [274, 240], [157, 225, 234], [225, 247], [233, 44], [89, 244], [80, 101], [210, 214], [78, 155], [55, 139], [102, 74, 75, 132], [105, 252], [149, 55, 59, 63, 71, 73, 81, 100, 102, 116, 122, 138, 146], [97, 231], [231, 97], [155, 78], [239, 305], [305, 239], [145, 94, 248], [147, 150], [61, 64], [152, 219], [219, 152], [246, 250], [252, 105], [223, 235], [235, 223], [237, 60, 344], [344, 237], [182, 129], [331, 117], [12, 2, 8, 10, 13, 15], [250, 246]]

def foo1(aa):
    aa = set(map(frozenset,a))  #eliminate duplicates
    return [x for x in aa if not any(x < y for y in aa)]

from itertools import takewhile
def conditional(x,aa,takewhile=takewhile):
    xlen = len(x)
    return any(x < y for y in takewhile(lambda z: xlen <= len(z),aa))

def foo2(aa):
    aa = sorted(set(map(frozenset,a)),key=len)
    return [x for x in aa if not conditional(x,aa)]

print set(foo1(a)) == set(foo2(a))

import timeit
N = 10000
print timeit.timeit('foo1(a)','from __main__ import foo1,a',number=N)
print timeit.timeit('foo2(a)','from __main__ import foo2,a',number=N)
于 2013-04-19T14:31:44.703 回答