Python嵌套列表内部比较和编辑

Question

我一直试图找出一些东西,最简单的解释方法是使用一个例子:

a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]

这是我开始的那种列表.我需要最终得到一个列表,其中包含包含重叠元素的所有列表的列表.

result = [[1, 2, 4, 5], [0, 3, 6, 7, 8, 12], [14, 18]]

我该怎么做？

亲切的问候,Daquicker

Answer 1

a = [[1, 2, 4], [2, 5], [0, 3, 7, 8], [12, 3, 6], [18, 14]]

result = []
for s in a:
    s = set(s)
    for t in result:
        if t & s:
            t.update(s)
            break
    else:
        result.append(s)

这将在列表中逐个进行,并从当前子列表(s)创建一个集合.然后它会检查结果,如果有另一个集合t与它有非空交集.如果是这种情况,则将项目s添加到该集合中t.如果没有t非空交集,那么它s是一个新的独立结果,可以附加到结果列表中.

像这样的问题也是定点迭代的一个很好的例子.在这种情况下,只要您仍然可以找到重叠的列表,您将查看列表并继续合并子列表.您可以使用itertools.combinations以查看成对的子列表来实现此目的:

result = [set(x) for x in a] # start with the original list of sets
fixedPoint = False # whether we found a fixed point
while not fixedPoint:
    fixedPoint = True
    for x, y in combinations(result, 2): # search all pairs …
        if x & y: # … for a non-empty intersection
            x.update(y)
            result.remove(y)

            # since we have changed the result, we haven’t found the fixed point
            fixedPoint = False

            # abort this iteration
            break