在列表列表中组合至少有一个共同数字的列表，Python

Question

考虑以下列表：

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ]

我想合并所有至少有一个共同数字的列表，这将被迭代地完成，直到它完成，没有dubletters。结果将是：

^{pr2}$

有没有什么好方法可以做到这一点，也许是使用itertools？在

Answer 1

out = []
for l in lists:
    for o in out:
        if set(l).intersection(set(o)):
            o[:] = list(set(l) + set(o))  # Mutate, don't reassign temp var
            break
    else:
        out.append(l)

写得不完美，可以优化，不排序，但应该给你如何做的想法。在

Answer 2

也许是这个？在

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ]
a, b = [], map(set, l)

while len(a) != len(b):
    a, b = b, []
    for x in a:
        for i, p in enumerate(b):
            if p & x:
                b[i] = p | x
                break
        else:
            b.append(x)        

print a
# [set([1, 2, 3, 4]), set([5, 6, 7, 8, 9])]

Answer 3

我天真的尝试：

1. 当交集不为空时合并所有元组
2. 对每个元组排序
3. 删除重复元组
4. 重复此操作，直到没有更多更改。在

---

示例：

def combine_helper(l):
    l = map(set, l)
    for i, x in enumerate(l, 1):
        x = set(x)
        for y in l[i:]:
            if x & y:
                x = x | y
        yield tuple(sorted(x))

def combine(l):
    last_l = []
    new_l = l
    while last_l != new_l:
        last_l = new_l
        new_l = list(set(combine_helper(last_l)))
    return map(list, last_l)

l = [ [1], [1], [1,2,3], [4,1], [5], [5], [6], [7,8,9], [7,6], [8,5] ]
print combine(l)

输出：

^{pr2}$