algorithm - 所有相交集的并集

给定具有多个属性的对象列表，我需要找到由所有相交子集的并集创建的集列表。
具体来说，它们是Person对象，每个都有许多属性我需要创建一个基于少数唯一标识符（如ssn、dln等）的“主”集列表。
例如，如果人员A和人员B具有相同的SSN，则创建集合I；如果人员B和人员C具有相同的DLN，则创建集合II。人D和E具有相同的SSN，但它（和所有其他标识符）与人A、B或C的任何标识符都不匹配。在合并所有相交子集之后，I将以一个集合与人A、B、C和另一个集合与人D、E结束。
这是我的解决方案的psuedo代码。我很好奇是否有人已经想出了一种更有效的方法来合并所有可能的相交集请记住，集合之间的链接可以是x个人长（即a matches b by ssn和b matches c by dln和c matches d by ssn和d matches e by某些其他标识符将导致a-e在一个集合中）。还假设这将在支持set操作中实现的语言。

bigSetList = array of all of the uniq Sets
fullyTested = false
while (bigSetList.size() > 1) or (fullyTested is false)
    foreach thisSet in bigSetList  order by size desc
        if count(sets that intersect with thisSet) > 0
            newThisSet = thisSet
            intersectingSets = []
            bigSetList.delete(thisSet)
            foreach testSet in bigSetList
                if thisSet.intersects(testSet)
                    newThisSet.addAll(testSet)
                    intersectingSets.push(testSetID)
                end if
            end
            bigSetList.delete(intersectingSets)
            bigSetList.push(newThisSet)
            bigSetList.sort()
            break
        end if
    end foreach
    fullyTested = true  // have looped through every set in the list and found 0 intersect partners
end

最佳答案

要在原始文章中展开我的评论，您需要创建一个集合列表，其中给定集合的每个成员至少与该集合的另一个成员共享一个属性。
天真地说，这可以通过查找共享一个属性的所有对和迭代地将具有相同伙伴的对合并在一起来解决。这将是o（n^3）（n^2用于在对上迭代，最多n个单独的集来确定成员资格）。
您还可以将此问题视为确定connected component of a graph，其中每个对象和每个唯一属性值都是一个节点；每个对象都将连接到其每个属性值建立该图需要线性时间，您可以通过广度或深度优先搜索来确定线性时间中的连接组件。

关于algorithm - 所有相交集的并集，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/967064/