有效比较项目的算法是成对列表

Question

我正在寻找以下问题的有效解决方案:

给定 1 个列表 L，每个列表包含对象 R。

L = [R1, R2, R3, .., Rn]

对象 R 可以相似也可以不相似。这是确定的通过函数 is_similar(R1, R2) 返回 True 以防它们是similar 否则为 False。

天真的做法是比较

R1-R2, R1-R3, ..., R1-Rn
R2-R3, R2-R4, ..., R2-Rn
...

我要指出的是

if is_similar(R1, R2) and is_similar(R2, R3)
then is_similar(R1, R3) <=> True
but if is_similar(R1, R2) <=> is_similar(R2, R1)

有什么算法可以解决这个问题吗？

Answer 1

您可以对元素对进行 n(n-1)/2 次可能的比较。

假设除了这些比较中的一个之外，您已经执行了所有比较，并且到目前为止所有比较都是错误的——一对未经测试的元素可能仍然相似或不相似。

这表明在最坏的情况下需要检查每一对可能的元素是否相等，因此不存在 o(n^2) 算法。

但总的来说，您可以比比较每一对元素做得更好。维护到目前为止发现的等价类列表，并且只将新元素与每个元素的代表进行比较。

在 Python 中是这样的:

E = []
for i in items:
    for e in E:
        if is_similar(i, e[0]):
            e.append(i)
            break
    else:
        E.append([i])

执行此代码后，E 将包含您的项目的等价类列表。