根据重叠项将列表的Python列表分组

Question

我有一个列表列表，我正试图根据它们的项目对它们进行分组或聚类。如果前一个组中没有元素，则嵌套列表将启动一个新组。在

输入：

paths = [  
        ['D', 'B', 'A', 'H'],  
        ['D', 'B', 'A', 'C'],  
        ['H', 'A', 'C'],  
        ['E', 'G', 'I'],  
        ['F', 'G', 'I']]

我的失败代码：

^{pr2}$

预期输出：

[
 [
  ['D', 'B', 'A', 'H'],
  ['D', 'B', 'A', 'C'],
  ['H', 'A', 'C']
 ],
 [
  ['E', 'G', 'I'],
  ['F', 'G', 'I']
 ]
]

另一个例子：

paths = [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['IP power', 'IP', 'power'],
         ['ARM', 'barrel', 'shifter']]

预期输出组：

output = [
         [['shifter', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'barrel shifter'],
         ['ARM', 'barrel', 'shifter']],
         [['IP power', 'IP', 'power']],
         ]

Answer 1

只要使用任何现有的聚类算法。说K-均值还是等级？在

http://en.wikipedia.org/wiki/K-means_clustering

http://en.wikipedia.org/wiki/Hierarchical_clustering

Answer 2

与Python中大多数以“我正在尝试按foo分组…”开头的问题一样，答案是“使用^{}和foo作为键。”

---

首先，让我们采用一个非常简单的分组标准：每个列表的长度。为此，键函数只是len。（您可能还想先sort，可能使用相同的键，这取决于您的数据。）

groups = [list(group) for key, group in itertools.groupby(paths, len)]

---

有时定义分组标准（因此定义键函数）很难，或者不可能根据每个元素的独立转换来定义。在这些情况下，groupby通常不是答案（尽管groupby加上另一个{}函数仍然可能是）。在

在这种情况下，定义分组标准的最自然的方法是与相邻元素进行比较。最简单的编写方法是编写一个比较两个相邻元素的cmp函数，然后在其上使用^{}：

^{pr2}$

Answer 3

您正在基于集合进行分组，因此请使用集合来检测新组：

def grouper(sequence):
    group, members = [], set()

    for item in sequence:
        if group and members.isdisjoint(item):
            # new group, yield and start new
            yield group
            group, members = [], set()
        group.append(item)
        members.update(item)

    yield group

这样可以得到：

^{pr2}$

或者你可以把它再放到一个列表中：

output = list(grouper(paths))

这假设组是连续的。如果有不相交的组，则需要处理整个列表，并循环到目前为止为每个项构建的所有组：

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]