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

Question

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

列表 L1 包含几个元素 [e_1,...,e_N]，可以与名为 areTheSame(e1,e2) 的通用函数进行比较。如果这个函数returnsTrue，说明两个元素属于同一个类别。

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

Answer 1

我相信您可以使用 itertools groupby 函数，但可能需要修改 areTheSame 函数，使其成为一个 keyfunc，即产生某种密钥。

L1 = sorted(L1, key=keyfunc)
L2 = [list(g) for _, g in groupby(L1, keyfunc))

Answer 2

假设函数是传递和反射的（如果不是，整个分组似乎没有多大意义），将每个词与每个组中的一个 "representative" 进行比较就足够了，例如只是第一个或最后一个元素。如果不存在这样的组，则创建一个新组，例如使用 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: ['lengths']}

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

Categorize elements of a list in python

python

list

categories

python-2.7