在Python中对列表元素进行分类

Question

我希望能够高效地对给定列表L1中的元素进行分类。该列表可能非常长，因此我正在寻找一种有效的方法来执行以下操作。

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

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

- Kikolo

---

我认为你可以在O(N**2)的时间内完成这个任务，首先找到所有独特的元素，然后在下一个循环中将相同类别的元素附加在其后。 - Marcus.Aurelianus

areTheSame 是否具有传递性和自反性？即，仅通过将每个元素与该组的任何一个代表进行比较就足以确定它是否属于该组？ - tobias_k

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'], ['一些', '带', '一些'], ['单词'], ['不同的'], ['长度']]

然而，这个算法的复杂度为 O(n*k)，其中 n 是单词数量，k 是分组数量。如果您有一个函数 getGroup(x) 而不是 areTheSame(x,y)，那么它将更加高效，因为您只需要 O(n) 的时间复杂度。也就是说，该函数会提取确定元素属于哪个组的属性。在我的例子中，这只是字符串的长度，但在您的情况下可能会更加复杂。

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：['不同']，7：['长度']}

- tobias_k

---

太好了！我不知道getGroup(x)会做什么。 - Kikolo

在我的例子中，getGroup（x）将只返回字符串的len。但很难说在你的情况下是否存在这样的键函数。把它想象成某种哈希函数，其中哈希对于任何一个组中的每个元素都是相同的。 - tobias_k

我认为在我的情况下getGroup(x)函数不存在。此外，我还面临着处理不可哈希元素的问题，因此它们不能用作d字典中的键。 - Kikolo

如果它们不能作为键，你可以使用一个列表的列表代替字典，然后将其与该列表中的第一个或最后一个元素进行比较，如果没有匹配项，则添加一个新列表。关于键/比较函数：你的函数是什么样子的，或者它确切地做了什么？ - tobias_k

@user3473823 我将第一个版本改为使用列表的列表，而不是字典，因为字典在这里并没有真正帮助，这样元素就不必是可哈希的。 - tobias_k

Answer 2

我相信你可以使用itertools groupby函数，但可能需要修改areTheSame函数使其成为键函数，即产生某种键。

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

- Tom Ron

---

将areTheSame转换为关键函数可能会很困难。根据函数，cmp_to_key可能有所帮助，但我认为这仅适用于函数返回0或-1/+1而不是True或False的情况。 - tobias_k