3

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

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

5 回答 5

4

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

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

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

于 2009-06-08T22:52:06.887 回答
0

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

于 2009-06-08T22:05:40.193 回答
0

因此，您的集合示例可能如下所示：

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

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

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

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

因为 α(n) 对于所有实际目的也是一个常数，所以总时间以 O(n 2 ) 为界。

于 2009-06-08T22:14:20.330 回答
0 
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;
                }
            }
    }
}
于 2009-06-08T22:20:37.980 回答
0

首先，标识符中是否存在一些固有的层次结构，并且较高类别的矛盾标识符是否会抵消较低类别的相同标识符？例如，如果 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对都是一个元素。您还有对应于objects 的元素。当您遍历对象的属性列表时，请执行 union (object, attribute)。

One of the important features of the Union-find data structure is that the resulting structure represents the set. It lets you query "What set is A in?" If this is not enough, let us know and we can improve the result.

But the most important feature is that the algorithm has something which resembles constant-time behavior for each union and query operation.

于 2009-06-09T23:08:45.230 回答