2

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

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

问题：

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

例如，给定 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}

在此处输入图像描述

与我原来的 nieve 算法相比，运行了 3 组：

在此处输入图像描述

4

1 回答 1

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();
于 2013-09-02T08:53:29.460 回答