一尘不染

所有相交集的并集

algorithm

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

具体来说,这些是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会在一个集合中产生Person
AE)。还假定将在支持集合操作中实现的语言。

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

阅读 235

收藏
2020-07-28

共1个答案

一尘不染

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

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

您也可以将这个问题认为是确定图的连接组件,其中每个对象和每个唯一属性值都是一个节点。每个对象都将连接到其每个属性值。设置该图将花费线性时间,并且您可以通过广度或深度优先搜索来确定线性时间中的连接组件。

2020-07-28