algorithm - 多组交集的算法模型

Question

我的问题是，我们如何申请 5~7 套的交集。假设每个集合都有一组元素。请帮助我为此创建一个算法，以及这个过程的复杂性。

Answer 1

假设集合的元素可以被散列，并且你有一些像字典这样的散列键工具（或者可以创建你自己的，这并不难）：

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 2

直截了当的方法：

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 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 的算法可以确定元素不在集合中，而无需搜索整个集合。