python - 组合列表中至少有一个共同点的列表，Python

Question

考虑这个列表列表：

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

我想合并所有至少有一个共同数字的列表，这将迭代地完成，直到它完成并且不会出现任何重复者。结果将是：

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

有没有什么巧妙的方法可以做到这一点，也许是使用 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)

输出：

$ python test.py
[[1, 2, 3, 4], [5, 6, 7, 8, 9]]

Answer 4

可以引入以下尝试：

1. 制作列表中存在单个值的 1 元素集列表。这是输出列表。
2. l 列表是如何连接输出列表中的项目的方法。例如，如果输出列表是[{1}, {2}, {3}]并且 l 列表中的第一个元素是[1,3]，那么输出列表中包含 1 和 3 的所有集合都应该连接：output = [{1,3}, {2}]。
3. 对 l 列表中的每个项目重复步骤 2。

代码：

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

def compose(l):
    # the following will convert l into a list of 1-element sets:
    # e.g. [ {1}, {2}, ... ]
    r = sum(l, [])
    r = map(lambda x: set([x]), set(r))

    # for every item in l
    # find matching sets in r and join them together
    for item in map(set, l):
        outside = [x for x in r if not x & item]  # elements untouched
        inside = [x for x in r if x & item]       # elements to join
        inside = set([]).union(*inside)           # compose sets 
        r = outside + [inside]
    return r

例子：

>>> compose(l)
[set([1, 2, 3, 4]), set([8, 9, 5, 6, 7])]

Answer 5

递归救援！不要忘记减少！

input_list = [ [1], [1], [1, 2, 3], [4, 1], [5], [5], [6], [7, 8, 9], 
               [7, 6], [8, 5] ]
def combine(input_list):
    input_list = map(set, input_list) # working with sets has some advantages
    reduced_list = reduce(combine_reduce, input_list, [])
    if len(reduced_list) == len(input_list):
        # return the whole thing in the original format (sorted lists)
        return map(sorted, map(list, reduced_list))
    else:
        # recursion happens here
        return combine(reduced_list)

def combine_reduce(reduced_list, numbers):
    '''
    find the set to add the numbers to or append as a new set.
    '''
    for sub_set in reduced_list:
        if sub_set.intersection(numbers):
            sub_set.update(numbers)
            return reduced_list
    reduced_list.append(numbers)
    return reduced_list

print combine(input_list)

打印出来：

$ python combine.py
[[1, 2, 3, 4], [5, 6, 7, 8, 9]]

我们这里有两件事。第一个是reduce：我正在使用它来整理列表，方法是将每个元素放入结果列表中的某个位置或附加它，如果这不起作用。但是，这并不能完成全部工作，所以我们重复这个过程（递归！），直到 reduce 不能提供更短的列表。

此外，使用set允许方便的intersection方法。您会注意到map(set, input_list)在递归中使用的行是多余的。combine从内部函数中提取包装函数combine_inner并将格式化/取消格式化（从list到set和返回）放置在外部函数中作为练习。