合并包含交集的列表

Question

鉴于：

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]

如何比较g中的每个列表，使具有共同数字的列表可以合并为一个集合？

例如：
0 存在于 g[2] 和 g[4] 中， 因此它们将合并为一个集合 {0，2，3，7}

我尝试了以下方法，但不起作用：

for i in g:
    for j in g:
        if k in i == l in j:
            m=set(i+j)

我想要创建一个尽可能大的集合。

- Na Lai

---

欢迎来到scicomp。由于您的问题比较Python特定，我建议您将其迁移到“stackoverflow”页面... - Jan

你能给出预期的输出吗？ - Bhargav Rao

这个回答是否解决了你的问题？Python：基于交集的简单列表合并 - Estif

Answer 1

作为一种更快的方法，您可以首先创建一个长度大于1的项目集合列表（s），然后遍历您的列表并使用union函数进行就地更新！

s=map(set,g)
def find_intersection(m_list):
    for i,v in enumerate(m_list) : 
        for j,k in enumerate(m_list[i+1:],i+1):
           if v & k:
              m_list[i]=v.union(m_list.pop(j))
              return find_intersection(m_list)
    return m_list

演示：

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
s=map(set,g)
print find_intersection(s)

[set([0, 2, 3, 7]), set([1, 4, 5, 6])]

g=[[1,2,3],[3,4,5],[5,6],[6,7],[9,10],[10,11]]
s=map(set,g)
print find_intersection(s)

[set([1, 2, 3, 4, 5, 6, 7]), set([9, 10, 11])]

g=[[], [1], [0,2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
s=map(set,g)
print find_intersection(s)

[set([1, 4, 5, 6]), set([0, 2, 3, 7])]

与 @Mark 的回答进行基准测试:

from timeit import timeit


s1="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]
sets = [set(i+j) for i in g for j in g if i!=j and (set(i) & set(j))]
    """
s2="""g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]

s=map(set,g)

def find_intersection(m_list):
    for i,v in enumerate(m_list) : 
        for j,k in enumerate(m_list[i+1:],i+1):
           if v & k:
              s[i]=v.union(m_list.pop(j))
              return find_intersection(m_list)
    return m_list 
    """

print ' first: ' ,timeit(stmt=s1, number=100000)
print 'second : ',timeit(stmt=s2, number=100000)

first:  3.8284008503
second :  0.213887929916

- Mazdak

---

你的算法是正确的，但实现中存在一个缺陷：尝试使用 g=[[], [1], [0,2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7]]。问题在于使用了 s[i:]，它创建了 s 的一个切片副本，而不会被 s.pop(t) 更新。 - Pablo Francisco Pérez Hidalgo

@PabloFranciscoPérezHidalgo 感谢您的留言，问题已解决。 - Mazdak

Answer 2

以下是一个快速的方法，可以列出所有相交的集合:

sets = [set(i+j) for i in g for j in g if i!=j and (set(i) & set(j))]

请注意，每个结果都会重复出现，因为每个列表都被比较了两次，一次在左侧，一次在右侧。

- Mark Ransom

---

在这种情况下，您可能希望执行以下操作：set(frozenset(i+j) for i in g for j in g if i!=j and (set(i) & set(j)))。它将消除重复项（假设这是OP想要的）。 - user2555451

抱歉，我能问一下 (set(i) & set(j) 是什么吗？ - James Harroid

@NaLai i 和 j 是 g 中的条目，它们是列表。set(i) 和 set(j) 是这些列表的集合版本。set(i) & set(j) 是 set(i) 和 set(j) 的交集。相应地，| 表示并集，^ 表示对称差异。 - senshin

@NaLai 请查看https://dev59.com/wnRB5IYBdhLWcg3wXmRI。如果两个集合的交集为空，则`if`语句将为false，否则为true。 - Mark Ransom

@iCodez 如何在不包含'frozenset'的情况下提取frozenset中的集合？ - James Harroid

@NaLai - "frozenset"这个词只在字符串表示中出现。你可以使用set()将frozensets转换为普通sets，但我认为这并不必要（除非你计划向sets中添加项目）。 - user2555451

Answer 3

如果g或g的元素很大，您可以使用不相交集来提高效率。

这种数据结构可以用来将每个元素分类到应该属于的集合中。

第一步是使用g中所有集合的索引构建一个带有标签的不相交集合集合：

g=[[], [], [0, 2], [1, 5], [0, 2, 3, 7], [4, 6], [1, 4, 5, 6], [], [], [3, 7],[99]]
g = map(set, g)
dss = CDisjointSets()
for i in xrange(len(g)):
    dss.MakeSet(i)

然后，当交集不为空时，集合被连接起来：

for i in xrange(len(g)):
    for j in xrange(i+1, len(g)):
        if g[i].intersection(g[j]):
            dss.Join(i,j)

此时，dss 为应该合并在一起的 g 集合提供了一个通用标签：

print(dss)

现在，您只需将具有相同标签的集合连接起来即可：

parent(0) = 0 parent(1) = 1 parent(2) = 2 parent(3) = 3 parent(4) = 2 parent(5) = 3 parent(6) = 3 parent(7) = 7 parent(8) = 8 parent(9) = 2 parent(10) = 10

l2set = dict()
for i in xrange(len(g)):
    label = dss.FindLabel(i).getLabel()
    l2set[label] = l2set.get(label, set()).union(g[i])
print(l2set)

导致如下结果：

{0: set([]), 1: set([]), 2: set([0, 2, 3, 7]), 3: set([1, 4, 5, 6]), 7: set([]), 8:   set([]), 10: set([99])}

这是我使用的不相交集实现，但你肯定可以找到另一个语法更好的实现：

""" Disjoint Sets
    -------------
    Pablo Francisco Pérez Hidalgo
    December,2012. """
class CDisjointSets:

    #Class to represent each set
    class DSet:
        def __init__(self, label_value):
            self.__label = label_value
            self.rank = 1
            self.parent = self
        def getLabel(self):
            return self.__label

    #CDisjointSets Private attributes
    __sets = None

    #CDisjointSets Constructors and public methods.
    def __init__(self):
        self.__sets = {}

    def MakeSet(self, label):
        if label in self.__sets: #This check slows the operation a lot,
            return False         #it should be removed if it is sure that
                                 #two sets with the same label are not goind
                                 #to be created.
        self.__sets[label] = self.DSet(label)

    #Pre: 'labelA' and 'labelB' are labels or existing disjoint sets.
    def Join(self, labelA, labelB):
        a = self.__sets[labelA]
        b = self.__sets[labelB]
        pa = self.Find(a)
        pb = self.Find(b)
        if pa == pb: 
            return #They are already joined
        parent = pa
        child = pb
        if pa.rank < pb.rank:
            parent = pb
            child = pa
        child.parent = parent
        parent.rank = max(parent.rank, child.rank+1)

    def Find(self,x):
        if x == x.parent:
            return x
        x.parent = self.Find(x.parent)
        return x.parent

    def FindLabel(self, label):
        return self.Find(self.__sets[label])

    def __str__(self):
        ret = ""
        for e in self.__sets:
            ret = ret + "parent("+self.__sets[e].getLabel().__str__()+") = "+self.FindLabel(e).parent.getLabel().__str__() + "\n"
        return ret

- Pablo Francisco Pérez Hidalgo