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

Question

我是一名有用的助手，可以为您翻译文本。

我有一个列表，其中包含多个列表，我正在尝试根据它们的项目对它们进行分组或聚类。如果前一组中没有任何元素，则嵌套列表将开始一个新组。 输入：

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

我的失败代码：

paths = [
    ['D', 'B', 'A', 'H'],
    ['D', 'B', 'A', 'C'],
    ['H', 'A', 'C'],
    ['E', 'G', 'I'],
    ['F', 'G', 'I']
]
groups = []
paths_clone = paths
for path in paths:
    for node in path:
        for path_clone in paths_clone:
            if node in path_clone:
                if not path == path_clone:
                    groups.append([path, path_clone])
                else:
                    groups.append(path)
print groups

预期输出：

[
 [
  ['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']],
         ]

- Shankar

---

什么定义了一个组？而paths_clone是对同一列表的引用，而不是副本。使用paths[:]来创建一个副本。 - Martijn Pieters

@MartijnPieters 这个组基本上是所有具有重叠项的列表。如上所示，我需要一种根据它们与其他列表共同拥有的项来对列表进行聚类的方法。 - Shankar

那么，当一个新的组开始时，是因为其中有一些项目没有出现在前一个组或前一个“项目”中吗？ - Martijn Pieters

@MartijnPieters 是的！之前的组。 - Shankar

Answer 1

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

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

这会给出以下结果：

>>> for group in grouper(paths):
...     print group
... 
[['D', 'B', 'A', 'H'], ['D', 'B', 'A', 'C'], ['H', 'A', 'C']]
[['E', 'G', 'I'], ['F', 'G', 'I']]

或者您可以将其再次转换为列表：

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]

- Martijn Pieters

---

@Martjin，我的输出结果不一样。我得到了4个组。我错在哪里了？[['D'，'B'，'A'，'H']] [['D'，'B'，'A'，'C']] [['H'，'A'，'C']，['E'，'G'，'I']] [['F'，'G'，'I']] - Shankar

@ArunprasathShankar：请检查您是否拥有相同的函数，因为一开始在那里出现了一个错误（一个not不应该在那里）。 - Martijn Pieters

@Martjin 你好Martjin，它在这种情况下失败了。路径为：[['shifter'，'barrel'，'barrel shifter']，['ARM'，'barrel'，'barrel shifter']，['IP power'，'IP'，'power']，['ARM'，'barrel'，'shifter']] 我得到了3组而不是两组 :( [['shifter'，'barrel'，'barrel shifter']，['ARM'，'barrel'，'barrel shifter']] [['IP power'，'IP'，'power']] [['ARM'，'barrel'，'shifter']] - Shankar

@ArunprasathShankar：给你了。 - Martijn Pieters

@Martjin 非常感谢您的帮助！！我发现使用networkx模块将列表转换为图形并提取connected_components是一种更简单的方法。 - Shankar

Answer 2

作为Python中大多数以“我想按foo分组…”开头的问题一样，答案是“使用foo作为键值，itertools.groupby函数”。首先，让我们来看一个非常简单的分组标准：每个列表的长度。对于此，键函数只需要len（您可能还想根据数据进行排序，可能使用相同的键）。

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

有时候，在每个元素上定义独立的转换来确定分组标准（因此也是关键函数）很困难，甚至不可能。在这些情况下，groupby 通常并不是答案（尽管 groupby 加另一个 itertools 函数仍可能是答案）。

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

def cmp_paths(lhs, rhs):
    return 0 if any(key in lhs for key in rhs) else -1
key_paths = functools.cmp_to_key(cmp_paths)
groups = [list(group) for key, group in itertools.groupby(paths, key_paths)]

- abarnert

---

defaultdict(list)是分组的另一种选择（其中foo是键）。其优点在于，不管输入是否经过排序，都可以通过O（N）操作进行分组。（但它需要键是可哈希的）。 - mgilson

@abamert 我不是想根据列表的长度对它们进行分组。我想根据列表之间重叠的项目对它们进行分组，就像上面的示例一样。 - Shankar

@ArunprasathShankar：“基于它们的项目”是什么意思？有哪些实际规则可以说明两个元素是否出现在同一组中？在任何人能够用Python理解之前，您需要以人类可以理解的方式进行解释。 - abarnert

@abarnert 对于之前不够明确的评论我表示歉意。现已更正，请再次查看。 - Shankar

我仍然不确定我是否理解了标准...但听起来你可以很容易地编写一个cmp函数，然后使用cmp_to_key将其转换为键。所以让我编辑答案。 - abarnert