联盟的所有交集

Question

给予一个名单的对象有多种属性的，我需要找到该名单的创建的一个联盟的所有交叉子集。

具体而言这些都是个人对象，每个都有许多属性。我需要建立一个列表中的"主"集基于少数的独特标识，例如SSN，从，等等。

例如，如果一个人和人B都有相同的SSN他们创造一套我.然后，如果人B和C有同样的从，他们创造一套二。人D和E中具有同样的社会安全号码但它(和所有其他标识符的)不符的任何标识符人A、B或C。合并后，所有交叉子我会结束了一组与人A、B、C和另一组与人D、E。

这里是伪码我的解决方案。我很好奇如果任何人已经想出了一个更有效的方式合并所有可能相交集。记得之间的联系，设置可能是X人长(即一个相匹配B由SSN和B相匹配的C和从C匹配D SSN和D匹配的电子通过某些其他标识将导致在人员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套独立的确定成员资格).

你也可以想想这个问题，因为确定 连接组成部分的曲线图, ，在那里每一个目和每一个独特的属性价值是一个节点；每个对象将是连接的每一个其特性的价值观。设立，图将采取线性时间，你可以确定的连接部件的线性时间与广度或深度第一次搜索。

Answer 2

我猜想你有一个相对较小的一组特性的人的对象(相比的人数对象你正在考虑).如果你想要的，以减少穿越清单的个人对象多次，你可以把一个人，把其属性变成一个已知的可能的连接，然后转移到下一个人。在每个连续的人，你看看它是否接到任何现有的连接。如果是这样，那么你增添其独特的属性，可能连接。你应该能够处理所有人的对象在一个通过。这是可能的，你会有一些断开集中的结果，因此可能值得审查的未连接的个人对象之后已经创建了第一个曲线图。

Answer 3

while (!people.isEmpty()) {
    Person first = people.get(0);
    people.remove(first);
    Set<Person> set = makeSet(first);
    for (Person person : people) {
        for (Person other : set) {
            if (person.isRelatedTo(other)) {
                set.add(person);
                people.remove(person);
            }
        }
    }
    sets.add(set);
}
for (Set<Person> a : sets) {
    for (Set<Person> b : sets.except(a)) {
        for (Person person : a)
            for (Person other : b) {
                if (person.isRelatedTo(other)) {
                    a.addAll(b);
                    b.clear();
                    sets.remove(b);
                    break;
                }
            }
    }
}

Answer 4

第一，有一些固有的层次结构中的识别符，并不矛盾的标识符的高排序取消出相同的标识符的较低的排序？例如，如果A和B都有相同的社会安全号码、B和C有同样从和C和D有相同的SSN不匹配A和B的SSN，这是不是意味着有两个团体或一个吗？

假设的矛盾并不重要，你正在处理的等同性课程，作为用户57368(未知Google)的国家。对于等价类，人们往往转向 联盟-找到 结构。至于如何执行这些工会，它不会立即微不足道，因为我假定你没有直接的链路A-B的时候A和B两者具有相同的SSN。相反，我们的设置将包括两种类的元素。每 (attribute type, attribute value) = attribute 对是一个元素。你也有对应的元素 objects.当你迭代表属性为对象，执行联盟 (object, attribute).

其中一个重要特点的联盟-找到的数据结构，所产生的结构表示设置的。它可以让你查询"什么样的设置是吗？" 如果这是不够的，让我们知道，我们可以提高的结果。

但最重要的特征是的算法具有的东西，它类似于恒定时的行为为各个联盟和查询的操作。

Answer 5

所以你收集的例子可以看起来是这样的：

A { ss |-> 42, dl |-> 123 }
B { ss |-> 42, dl |-> 456 }
C { ss |-> 23, dl |-> 456 }
D { ss |-> 89, dl |-> 789 }
E { ss |-> 89, dl |-> 432 }

然后我建议使用一种算法，其中你建立多集合，通过逐步合并或插入每一个收集到的多集合：

迭代1.第一个集合成为唯一的多集合：

{A} { ss |-> [42], dl |-> [123] }

迭代2.合并的下一个收集到的第一个，因为社会安全号码是已经存在：

{A,B} { ss |-> [42], dl |-> [123,456] }

迭代3.再次合并，因为从已经有：

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }

迭代的4.插入一个新的多收集由于没有匹配：

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D}     { ss |-> [89],    dl |-> [789]     }

迭代5.合并的第二多的收集，由于社会安全号码是：

{A,B,C} { ss |-> [23,42], dl |-> [123,456] }
{D,E}   { ss |-> [89],    dl |-> [432,789] }

因此，在每次迭代(每一个用于收集)，必须确定 所有 多集有价值的共同与集合你都处理和合并 所有 这些在一起。

在一般情况下，如果有n集每一个恒定k数量的属性，那么这个算法将运行在时间O(研究)=O(n²).最糟糕的情况下，行为是exibited如果所有特性的价值观是不同的。当有更多的共享之间的属性值，所需的时间插入，并确定成员资格在属性价值的集(如[23,42])获取至是主导因素，因此属性价值的设置应该是有效的。

如果你使用 最佳的相交集, 然后每个发现或合并操作将运行在时间分摊O(α(n))。

因此，对于每一次迭代将有至多n多集的(这种情况时，没有多收藏已经被合并到目前为止).将新的收入多收藏，你将不得不执行一个找到的操作上的每一个多集k组，以确定所有多集加以合并，这需要时间界O(恩卡(n))。合并在最k多集中找到这种方式需要O(k²α(n))。

因此，对于所有迭代的时间为界O(n(恩卡(n)+k²α(n)))=O(n(恩卡(n)))=O(n²カ(n))=O(n²α(n))由于k的一个恒定不变。

因为α(n)对于所有的实际目的来说也是一个恒定的，总的时间被界O(n²).