所有相交集的并集

Question

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

具体来说，这些是 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，将导致一组中出现人员 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

Answer 1

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

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

您还可以将此问题视为确定图的连通分量，其中每个对象和每个唯一的属性值都是一个节点； 每个对象都将连接到它的每个属性值。 设置该图需要线性时间，您可以通过广度或深度优先搜索在线性时间内确定连接的组件。

Answer 2

我猜想您的 Person 对象有一组相对较小的属性（与您正在考虑的 Person 对象的数量相比）。 如果要减少多次遍历 Person 对象列表，可以获取一个 Person，将其属性放入已知可能连接的列表中，然后继续处理下一个 Person。 对于每个连续的 Person，您可以查看它是否与任何先前的连接有关。 如果是这样，那么您可以将其独特的属性添加到可能的连接中。 您应该能够一次性处理所有 Person 对象。 结果中可能会有一些断开连接的集合，因此在创建第一个图后检查未连接的 Person 对象可能是值得的。

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 具有相同的 SSN，B 和 C 具有相同的 DLN，并且 C 和 D 具有相同的 SSN，但与 A 和 B 的 SSN 不匹配，这是否意味着有两个组或一个？

假设矛盾并不重要，您正在处理等价类，正如用户 57368（未知的 Google）所述。 对于等价类，人们经常转向 Union-find 结构。 至于如何执行这些联合，这并不是一件小事，因为我假设当 A 和 B 具有相同的 SSN 时，您没有直接链接 AB。 相反，我们的集合将由两种元素组成。 每个(attribute type, attribute value) = attribute 对都是一个元素。 您还拥有与 object 相对应的元素。 当您迭代对象的属性列表时，请执行联合(object, attribute)。

并查数据结构的重要特征之一是结果结构代表集合。 它可以让你查询“A 属于哪个集合？” 如果这还不够，请告诉我们，我们可以改进结果。

但最重要的特征是该算法具有类似于每个联合和查询操作的恒定时间行为。

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. 由于 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²)。 如果所有属性值都不同，则会出现最坏情况的行为。 当属性值之间有更多共享时，插入和确定属性值集（如[23,42]）中的成员资格所需的时间将成为主导因素，因此属性值集应该是高效的。

如果您使用最佳不相交集，则每个查找或合并操作将在摊销时间内运行O(α(n))。

因此，对于每次迭代，最多会有 n 个多重集合（到目前为止还没有合并多重集合的情况）。 要将新集合集成到多集合中，您必须对每个多集合 k 集执行查找操作，以识别要合并的所有多集合，这需要 O(nkα(n)) 的时间。 要合并以这种方式找到的最多 k 个多重集合，需要 O(k²α(n))。

因此，对于所有迭代，时间都受 O(n(nkα(n)+k²α(n))) = O(n(nkα(n))) = O(n²kα(n)) = O(n²α(n)) 因为 k 是一个常数。

由于 α(n) 在所有实际用途中也是一个常数，因此总时间受 O(n²) 限制。