python - 根据重复项对 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

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

(因为使用了字典，不能保证顺序。)