所有组相交联盟 [英] Union of All Intersecting Sets

问题描述

考虑到与我需要找到所有相交的子集的联合创建集列表多个属性的对象的列表。

具体而言，这些都是Person对象，每个都有很多属性。我需要创建的基础上一把唯一标识符，如SSN，DLN等大师集列表。

例如，如果某甲和某乙具有相同的SSN他们创造了一组我。然后，如果人B和C具有相同的DLN，他们创造了一套二。人D和E具有相同的SSN，但它（和所有其他标识符）不符合任何人的A，B或C的标识符合并所有相交的子集，我将结束与一组与人员A，B，C后，而另一组人D，E。

下面是psuedo- $ C $下我的解决方案。我很好奇，如果有人已经提出了合并所有可能的组相交的更有效的方法。请记住，集合之间的联系可以为X的人长（即A由SSN匹配B和B通过DLN匹配C和C由SSN匹配D和D由其他标识符匹配ê会导致人员AE在一组）。此外，假定这将在支持实施语言设置操作。

  bigSetList =所有的uniq集的数组
fullyTested = FALSE
而（bigSetList.size（）→1）或（fullyTested为假）
    的foreach thisSet在bigSetList顺序按大小降序
    如果count（套与thisSet相交）＆GT; 0
    newThisSet = thisSet
    intersectingSets = []
    bigSetList.delete（thisSet）
    在bigSetList的foreach testSet
    如果thisSet.intersects（testSet）
    newThisSet.addAll（testSet）
    intersectingSets.push（testSetID）
    如果结束
    		结束
    bigSetList.delete（intersectingSets）
    bigSetList.push（newThisSet）
    bigSetList.sort（）
    		打破
    如果结束
    年底的foreach
    fullyTested = TRUE //已通过每一个组在列表中循环，发现0相交的合作伙伴
结束
 

解决方案

要扩大我在原来的职位评论，你要创建的集列表，其中的一组给定的股票每个成员至少有一个属性至少有该组的一名其他成员。

天真，这既可以通过寻找共享的属性的所有对和合并对一起具有相同伙伴迭代求解。这将是O（N ^ 3）（N ^ 2用于遍历对，以及多达N个独立组来确定会员）。

您也可以把这个问题作为确定href="http://en.wikipedia.org/wiki/Connected%5Fcomponent%5F%28graph%5Ftheory%29" rel="nofollow">连接组件的，其中每一个物体和独特的属性值是一个节点;每个对象将被连接到它的每个属性值。设置该图将需要线性时间，你可以用一个广度和深度优先搜索确定线性时间的连接部分。

Given a list of objects with multiple attributes I need to find the list of sets created by a union of all intersecting subsets.

Specifically these are Person objects, each with many attributes. I need to create a list of 'master' sets based on a handful of unique identifiers such as SSN, DLN, etc.

For instance, if Person A and Person B have the same SSN they create a set i. Then if Person B and C have the same DLN, they create a set ii. Person D and E have the same SSN but it (and all other identifiers) does not match any of the identifiers of Persons A, B or C. After merging all intersecting subsets I would end up with one set with Persons A,B,C and another set with Persons D, E.

Here is the psuedo-code for my solution. I am curious if anyone has already come up with a more efficient way of merging all possible intersecting sets. Keep in mind that the links between sets could be X Persons long (i.e. A matches B by SSN and B matches C by DLN and C matches D by SSN and D matches E by some other identifier would result in Persons A-E in one set). Also assume that the language this will be implemented in supports set operations.

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

解决方案

To expand on my comment in the original post, you want to create a list of sets where each member of a given set shares at least one attribute with at least one other member of that set.

Naively, this can be solved either by finding all pairs that share an attribute and merging pairs together that have the same partner iteratively. This would be O(N^3) (N^2 for iterating over pairs, and up to N separate sets to determine membership).

You can also think of this problem as determining the connected component of a graph, where every object and every unique attribute value is a node; each object would be connected to each of its attribute values. Setting up that graph would take linear time, and you could determine the connected components in linear time with a breadth or depth first search.

这篇关于所有组相交联盟的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！