计算不定数量集合的所有相交和不相交的算法

Question

最近我不得不为下面概述的集合问题开发一个朴素的递归算法，但现在想知道问题的正式描述/名称是什么，以及是否有一种算法可以更有效地解决问题(我怀疑有)。

我知道有单独的算法来查找相交和不相交，但我还没有发现任何可以涵盖整个问题的算法。

问题:

获取无限数量的集合并为所有集合的每个相交和不相交返回一个集合。

例如，给定 4 个集合作为输入 A、B、C、D:

一个{1,14,2,10,13,12,8,9}

B {2,3,4,15,11,13,9}

C {13,10,4,15,5,6,12,11}

D {7,8,9,13,11,6,12}

结果应该是以下13组:

{1,14},{2},{3},{4,15},{5},{6},{7},{8},{9},{10},{11} ,{12},{13}

我开发的算法很天真，因为它递归地比较所有集合排列(我希望能够在 XSLT 2.0 中相对容易地实现这一点)，直到找不到进一步的交集。

在某些情况下，我需要执行此操作来描述树的多个版本如何在树上的每个点修改原始树。 “树”实际上是一个 XML 文档。

[更新]显示针对 3 个集合运行的已接受答案中的第一个算法:{1,2,3},{2,3,4},{2,3,5}

与我在 3 组上运行的原始 nieve 算法相比:

Answer 1

一旦明确了一些设置属性，问题就变得很简单。

A int B int C = ( A int B ) int C

这告诉我们，我们可以解决 2 个集合的问题，然后将每个结果与第三个集合相交，依此类推。

通过解决 hte 问题，我的意思很简单，A int B 生成 3 个集合:

A op B => A int B , A - (A int B) , B - (A int B)

一旦明确了这一点，实现就很简单了，应该如下所示:

resultset = emptyset
while ( queue not empty )
   tmpset = emptyset
   A = queue.pop()
   residual = A
   for B in resultset
     tmpset = tmpset + {A int B , B - (A int B)}
     residual = residual - B
   tmpset = tempset + residual
   resultset = tmpset

显然，如果集合中的任何一个为空，则不需要将其添加到解决方案中。这是一些使用字典思想解决问题的 C# 代码:

        var query = arr.Select((x, i) => x.Select(y => new { Elem = y, Index = i }))
            .SelectMany(x => x)
            .GroupBy(x => x.Elem)
            .ToDictionary(x => x.Key, y => new HashSet<int>(y.Select(z => z.Index).ToList()))
            .GroupBy(x => x.Value, HashSet<int>.CreateSetComparer())
            .Select(x=>x.Select(y=>y.Key).ToList())
            .ToList();