多个集合求交的算法模型

Question

我的问题是，我们如何才能应用5~7个集合的交集。假设每个集合都有一组元素。请帮助我创建一个算法，这将是这个过程的复杂性。

Answer 1

一种直接的方法：

I = S_1;
For each set s in S_2 ... S_N:
    For each element ei in I:
      if ei not in s
        remove ei from I
      endif
    endfor
endfor

这样，如果每个集合有m个元素，并且有N个集合，则复杂度为m^2xN。如果集合是排序的，那么您可以使用二进制搜索获得mlog(m)N，甚至可以通过在排序的情况下提前两个迭代器来获得O(mN)。

Answer 2

假设集合的元素可以散列，并且您有一些Hash-Key工具，如字典(或者可以创建自己的，这并不难)：

List<Set<element-type>> sets;    \\your list of sets to intersect

int size = SUM{List[*].Count};  \\ size for the hash
Dictionary<element-type,int> Tally = New Dictionary<element-type,int>(size);

// Add all elements to the Tally hash
foreach set in sets
{
    foreach e in set
    {
        if (Tally.Exists(e))
            Tally[e]++;
        else
            Tally.Add(e,1);
    }
}

//Now, find the Tally entries that match the number of sets
foreach kvp in Tally.KeyValuePairs
{
    If (kvp.Value == sets.Count)
        // add the Key to output list/set
        Output.Add(kvp.Key);
}

这具有运行时复杂度O(n)，其中"n“是所有集合中元素的数量。

Answer 3

现在，我将假设集合被表示为列表，并且它们开始时是未排序的。

(编辑以使我的符号符合@perreal的符号)

给定N个集合中总共有m*N个项目，可以将集合连接到单个列表中(m*N个操作)，对列表进行排序(m*N个log m*N个操作)，然后遍历排序后的列表，保留列表中恰好有N个副本的任何项目(另一个m*N个操作)，对于任何情况，给出(我认为)总计m*N (2 + log m*N)个操作。

通过比较，假设每个集合都有相同数量的项目m，我认为如果所有集合都相同，@perreal的解决方案将是最多m^2*N次操作。对于较大的m*N值，这将需要比我的算法更多的m*N (2 + log m*N)操作。然而，在最好的情况下，@perreal的解决方案只需要2m*N操作(如果测试的第一个和第二个集合没有交集)。

如果按大小递增的顺序比较集合，则@perreal的解决方案对于交集较小的情况也需要较少的操作，其中S_1是最小的集合。

如果集合从排序列表开始，两种解决方案都会更快，因为我的算法不需要初始排序，并且@perreal的算法可以确定元素不在集合中，而不必搜索整个集合。