多个集合的交集算法模型

Question

我的问题是，如何对5~7个集合应用交集。假设每个集合都有一组元素。请帮我创建一个算法，并说明这个过程的复杂度。

- Mallikharjuna Rao

---

假设这些集合被存储在数组中，那么这些数组是否已排序？ - uba

元素是什么意思？整数、字符串还是其他类型？ - amin k

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)的复杂度。

- perreal

---

首先通过最小计数找到集合，时间复杂度为O(n)。对于此集合中的每个项进行搜索。 - amin k

Answer 2

假设集合中的元素可以被哈希，并且您有某个类似于字典的哈希键设施（或者可以创建自己的设施，这不难）：

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”是所有集合中元素的数量。

- RBarryYoung

Answer 3

我暂时假设集合以列表形式表示，并且开始时未排序。

给定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次操作。

如果按大小顺序逐个比较集合，并使S_1成为最小的集合，则@perreal的解决方案在交集较小的情况下也需要更少的操作。

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

- Simon

---

你确定你能排序吗？ - amin k

@amink：这是一个很好的观点——我的算法要求集合的元素具有一致的排序顺序。如果你只能比较元素的相等性，那么perreal的解决方案会更好。 - Simon