根据重复项对 Python 个列表进行分组

Question

这个问题与这个问题非常相似Group Python list of lists into groups based on overlapping items，实际上它可以被称为重复。

基本上，我有一个子列表列表，其中每个子列表包含一些整数（这个数字在子列表中是不一样的）。我需要对共享一个或多个整数的所有子列表进行分组。

我问一个新的单独问题的原因是因为我试图改编 Martijn Pieters 的 great answer 但运气不好。

这是 MWE：

def grouper(sequence):
    result = []  # will hold (members, group) tuples

    for item in sequence:
        for members, group in result:
            if members.intersection(item):  # overlap
                members.update(item)
                group.append(item)
                break
        else:  # no group found, add new
            result.append((set(item), [item]))

    return [group for members, group in result]


gr = [[29, 27, 26, 28], [31, 11, 10, 3, 30], [71, 51, 52, 69],
      [78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81],
      [86, 68, 67, 84]]

for i, group in enumerate(grouper(gr)):
    print 'g{}:'.format(i), group

我得到的输出是：

g0: [[29, 27, 26, 28]]
g1: [[31, 11, 10, 3, 30]]
g2: [[71, 51, 52, 69]]
g3: [[78, 67, 68, 39, 75], [84, 67, 78, 77, 81], [86, 68, 67, 84]]
g4: [[86, 84, 81, 82, 83, 85]]

最后一组 g4 应该与 g3 合并，因为其中的列表共享项目 81、83 和 84，甚至一个重复的元素也足以让它们合并。

我不确定是我应用的代码有误，还是代码有问题。

Answer 1

如果您将每个子列表变成一个集合，听起来像是集合合并，因为您对内容而不是顺序感兴趣，所以集合是最好的数据结构选择。看到这个：http://rosettacode.org/wiki/Set_consolidation

Answer 2

您可以将要执行的合并描述为集合合并或连通分量问题。我倾向于使用现成的集合合并算法，然后根据特定情况对其进行调整。例如，IIUC，您可以使用

def consolidate(sets):
    # http://rosettacode.org/wiki/Set_consolidation#Python:_Iterative
    setlist = [s for s in sets if s]
    for i, s1 in enumerate(setlist):
        if s1:
            for s2 in setlist[i+1:]:
                intersection = s1.intersection(s2)
                if intersection:
                    s2.update(s1)
                    s1.clear()
                    s1 = s2
    return [s for s in setlist if s]

def wrapper(seqs):
    consolidated = consolidate(map(set, seqs))
    groupmap = {x: i for i,seq in enumerate(consolidated) for x in seq}
    output = {}
    for seq in seqs:
        target = output.setdefault(groupmap[seq[0]], [])
        target.append(seq)
    return list(output.values())

这给出了

>>> for i, group in enumerate(wrapper(gr)):
...     print('g{}:'.format(i), group)
...     
g0: [[29, 27, 26, 28]]
g1: [[31, 11, 10, 3, 30]]
g2: [[71, 51, 52, 69]]
g3: [[78, 67, 68, 39, 75], [86, 84, 81, 82, 83, 85], [84, 67, 78, 77, 81], [86, 68, 67, 84]]

（因为使用了词典，所以顺序不保证。）

根据重复项对 Python 个列表进行分组

Group Python lists based on repeated items

python

algorithm

grouping