代码之家 › 专栏 › 技术社区 › Jeff Swensen

所有交叉装置的联合

set-union set-intersection language-agnostic set algorithm

Jeff Swensen · 技术社区 · 17 年前

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

具体来说,这些是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

5 回复 | 直到 17 年前

MSN 17 年前

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

Bernard Chen 17 年前

Carl Manaster 17 年前

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;
                }
            }
    }
}

Martin Hock 17 年前

Union-find 结构。至于如何执行这些联合,这并不是一件小事,因为我假设当A和B都有相同的SSN时,你没有直接的链接A-B。相反,我们的集合将由两种元素组成。每 (attribute type, attribute value) = attribute object (object, attribute) .

jpsecher briankip 16 年前

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。将下一个集合合并到第一个集合中,因为SSN已经存在:

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

迭代3。再次合并,因为DLN已经存在:

{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。与第二个多集合合并,因为SSN存在:

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

全部与您正在处理的集合具有共同值的多个集合,并合并全部

一般来说,如果有n个集合,每个集合都有恒定的k个属性,那么该算法将在时间O(nnk)=O(n ^2.

optimal disjoint sets ,则每个查找或合并操作将在摊销时间O(α(n))内运行。

^2. α(n))。

^2. α(n))=O(n(nkα(n ^2. ^2.

因为α(n)在所有实际应用中也是一个常数,所以总时间受O(n)的限制 ^2. ).