python - 对现有项目列表进行排序以比较聚类解决方案

Question

我有一个小的排序问题。我正在比较数千个集群解决方案以查找和计算相同的解决方案。我遇到的问题如下:

给定两个集群解决方案:

l1 = [1,1,1,2,2,3,3,2,2]
l2 = [2,2,2,1,1,3,3,1,1]

这两个解决方案是相同的，但组标签不同。如何对 l2 进行排序以使其看起来像 l1？我想这样做是为了让散列更容易。

Answer 1

我想我理解你的问题，像下面的函数这样的东西会起作用，我认为你很难在不到 O(n) 的时间内完成它。

def normalize_groups(in_list):
    groups = {}
    output = []
    for value in in_list:
        if value not in groups:
            groups[value] = len(groups)
        output.append(groups[value])
    return output

这将返回两个列表:

In [52]: normalize_groups(l1)
Out[52]: [0, 0, 0, 1, 1, 2, 2, 1, 1]

In [53]: normalize_groups(l2)
Out[53]: [0, 0, 0, 1, 1, 2, 2, 1, 1]

编辑:没关系，完全删除字符串部分。