折叠列表以消除冗余

Question

我有几个相关对象的长列表，我想将它们分组以减少冗余。伪代码：

>>>list_of_lists = [[1,2,3],[3,4],[5,6,7],[1,8,9,10]...]
>>>remove_redundancy(list_of_lists)
[[1,2,3,4,8,9,10],[5,6,7]...]

因此，包含相同元素的列表将被折叠成单个列表。折叠它们很容易，一旦我找到要组合的列表，我就可以将它们组合成一组，并进行合并，但我不确定如何比较这些列表。我需要执行一系列for循环吗？在

我的第一个想法是，我应该循环检查子列表中的每一项是否在其他列表中，如果是，则合并这些列表，然后重新开始，但这似乎非常低效。我做了一些搜索，发现了这个：Python - dividing a list-of-lists to groups但是我的数据不是结构化的。而且，我的实际数据是一系列字符串，因此在任何意义上都不可排序。在

我可以编写一些复杂的循环代码来实现这一点，但我想知道是否有任何内置函数可以使这种比较更容易。可能是list comprehensions里的东西？在

Answer 1

如果我能正确理解你的问题，我认为这是一个相当有效的方法。这里的结果是一个集合列表。在

也许缺少的知识是d & g（也写了d.intersection(g)）来寻找集合交集，以及在Python中一个空集是“错误的”

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

result = []

for d in data:
    d = set(d)

    matched = [d]
    unmatched = []
    # first divide into matching and non-matching groups
    for g in result:
        if d & g:
            matched.append(g)
        else:
            unmatched.append(g)
    # then combine all matching groups into one group
    # while leaving unmatched groups intact
    result = unmatched + [set().union(*matched)]

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

我们从根本不分组开始（result = []）。然后我们从数据中提取第一个列表。然后我们检查哪些现有的组与该列表相交，哪些不相交，然后将所有这些匹配的组与列表合并（从matched = [d]开始实现）。我们不涉及不匹配的组（尽管其中一些可能会在以后的迭代中被合并）。如果您在每个循环中添加一行print(result)，您应该能够看到它是如何构建的。在

matched中所有集合的并集由set().union(*matched)计算。供参考：

• Pythonic Way to Create Union of All Values Contained in Multiple Lists
• What does the Star operator mean?

Answer 2

我假设您希望合并包含任何公共元素的列表。在

如果任何两个列表至少包含一个公共元素（根据==运算符），那么这个函数看起来非常有效（据我所知）

import functools #python 2.5+
def seematch(X,Y):
    return functools.reduce(lambda x,y : x|y,functools.reduce(lambda x,y : x+y, [[k==l for k in X ] for l in Y]))

如果您使用一个reduce，当您发现“true”时可以中断，则会更快，如下面所述： Stopping a Reduce() operation mid way. Functional way of doing partial running sum

我试图找到一种优雅的方法来快速迭代，但是我认为一个好的方法就是简单地循环一次，然后创建一个包含“合并”列表的其他容器。对原始列表中包含的列表以及在代理列表上创建的每个新列表循环一次。在

话虽如此，但似乎还有一个更好的选择，看看你是否可以通过在前面的步骤上做一些簿记来消除这种冗余。在

我知道这是一个不完整的答案-希望有帮助！在