python - 在python中对列表的元素进行分类

Question

我想有效地对给定列表 L1 的元素进行分类。此列表可以任意长，因此我正在寻找一种有效的方法来执行以下操作。

列表 L1 包含多个元素 [e_1,...,e_N] 可以与名为 areTheSame(e1,e2) 的通用函数进行比较。如果此函数返回 True，则表示两个元素属于同一类别。

最后，我想要另一个列表 L2，它又包含不同的列表 [LC_1, ..., LC_M]。每个 LC 列表包含同一类别的所有元素。

Answer 1

假设函数是传递和反射的(如果不是，整个分组似乎没有多大意义)，将每个词与每个组中的一个“代表”进行比较就足够了，例如只是第一个或最后一个元素。如果不存在这样的组，则创建一个新组，例如使用带有空列表的 next 作为默认元素。

lst = "a list with some words with different lengths".split()
areTheSame = lambda x, y: len(x) == len(y)
res = []
for w in lst:
    l = next((x for x in res if areTheSame(w, x[0])), [])
    if l == []:
        res.append(l)
    l.append(w)

结果:[['a'], ['list', 'with', 'some', 'with'], ['words'], ['different'], ['lengths'] ]

尽管如此，这仍然具有 O(n*k) 的复杂度，其中 n 是单词的数量，k 是组的数量。如果您使用函数 getGroup(x) 而不是 areTheSame(x,y) 会更高效，那么您将拥有 O(n)。也就是说，该函数不是测试两个元素是否属于同一组，而是提取确定该元素属于哪个组的属性。在我的例子中，这只是字符串的 len，但在你的例子中它可能更复杂。

getGroup = lambda x: len(x)
d = collections.defaultdict(list)
for w in lst:
    d[getGroup(w)].append(w)

结果:{1: ['a'], 4: ['list', 'with', 'some', 'with'], 5: ['words'], 9: ['different '], 7: ['长度']}