4

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

输入： 

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

2 回答 2

5

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

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]
于 2013-04-30T18:06:14.430 回答
4

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

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

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)]
于 2013-04-30T17:55:08.987 回答