algorithm - 所有相交集的并集

Question

给定一个具有多个属性的对象列表，我需要找到由所有相交子集的并集创建的集合列表。

具体来说，这些是 Person 对象，每个对象都有许多属性。我需要根据一些唯一标识符(例如 SSN、DLN 等)创建“主”集列表。

例如，如果 A 和 B 具有相同的 SSN，则他们创建一个集合 i。然后，如果 B 和 C 具有相同的 DLN，则他们创建一个集合 ii。 D 和 E 具有相同的 SSN，但它(以及所有其他标识符)与 A、B 或 C 的任何标识符都不匹配。在合并所有相交的子集后，我最终会得到一个包含 A、B、C 的集合另一组是 D、E。

这是我的解决方案的伪代码。我很好奇是否有人已经想出一种更有效的方法来合并所有可能的相交集。请记住，集合之间的链接可能是 X 人长(即 A 通过 SSN 匹配 B，B 通过 DLN 匹配 C，C 通过 SSN 匹配 D，D 通过其他标识符匹配 E 将导致一组中的人 A-E)。还假设将在其中实现的语言支持集合操作。

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

Answer 1

为了扩展我在原始帖子中的评论，您想要创建一个集合列表，其中给定集合的每个成员至少与该集合的另一个成员共享至少一个属性。

天真地，这可以通过找到所有共享属性的对并迭代地将具有相同伙伴的对合并在一起来解决。这将是 O(N^3)(N^2 用于迭代对，以及最多 N 个单独的集合以确定成员资格)。

您也可以将此问题视为确定 connected component of a graph ，其中每个对象和每个唯一属性值都是一个节点；每个对象都将连接到它的每个属性值。设置该图需要线性时间，您可以通过广度或深度优先搜索在线性时间内确定连通分量。