algorithm - 从至少有两个元素相等的列表中找出所有最大的子列表

Question

给定一个对象列表和一个非传递相等函数，该函数在两个对象相等时返回 true，否则返回 false，我需要找到至少有两个对象相等的所有最大子列表。例如 -

val list = List(o1, o2, o3, o4, o5)

和，

isEqual(o1, o2) => true
isEqual(o2, o4) => true
isEqual(o3, o5) => true

结果将是:

List(o1, o2, o4)
List(o3, o5)

请注意 isEqual 是不可传递的，即在上述情况下 o1 可能不等于 o4，即使它们属于同一个子列表。

Answer 1

你的问题等同于找到图的所有连通分量的问题。

首先要做的是，将列表转换为图 G(V, E)，其中 V 代表顶点，E 代表边:

V = list
E = {(o1,o2) for all o1,o2 in list| o1.Equals(o2)}

然后做一个DFS来找到所有的组件

WHILE-EXISTS unvisted node in G DO
     component[i] = DFS(G)
END

当然，组件是 Graphs 本身。 组件是您要查找的列表，组件中的顶点是列表的元素。

对于您的示例，图表看起来像这样

注意:由于您必须比较每个对象，因此对话将花费 O(n^2)。 找到所有组件需要 O(n)。所以这个算法的渐近运行时间为 O(n^2)

Answer to the comment in your question

Since the conversion of your problem to this graph problem seems correct, I am pretty sure it is not possible. If you see it as a graph, you simply have to check each node if it is connected with each other node. You also can not stop after you find one equal node, because you maybe will find another node which is equal and by stoping, you would split the connected component.