给定具有多个属性的对象列表,我需要找到由所有相交子集的并集创建的集合列表。
具体来说,这些是 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,这将导致 Persons 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