2个联合/交集，其中每个集合由其子集定义

Question

我们从其他集合的联合中知道每个集合的定义。

例如

A = B union {1,2}

B = C union D

C = {5,6}

D = {5,7}

E = {4}

然后A = {1,2,5,6,7}

联盟E = {1,2,4,5,6,7}

是否有任何有效的算法可以做到这一点。假设联合的层次结构可能非常深，并且子集可以经常更改（不是那么多）。 我认为应该有办法尽量减少必须做出的工会数量。

Answer 1

所以你有一套不变的变化集合的层次结构？在你的例子中，你只对一组的价值感兴趣吗？

然后展平层次结构。也就是说，在您的示例中，您将一次遍历层次结构以查找您的集合是其并集的更改集的集合，并存储此集合。

要在叶集更改时免除重新计算联合，您可以跟踪每个元素当前包含的集数。如果叶集更改，则可以快速更新，而不需要查看任何未更改的叶集。然后，那些频率计数> 1的元素。 0目前正在加入。

Answer 2

也许您正在寻找某种不相交集数据结构？

Answer 3

关于此案的几个问题。

第一个问题：这个“脚本”有多长？ /“程序”必须跑吗？如果它不是太长，在执行联合操作之前简单地存储先前的联合并检查缓存可能是一个很好的选择。现在的记忆并不昂贵:)。

你应该问的第二个问题：在工会之前是否按某种顺序排列？如果不是，并且列表被多次访问，则首先对列表进行排序非常有用（例如，当您只在列表的一半时可以做出决定）。 Mergesort 是一种有效连接两个有序列表的强大技术。