快速搜索集合数组的方法

Question

我有一个包含100,000个集合的数组。每个集合包含1,000,000以下的自然数。我必须找到有序对的数量{m，n}，其中0

例如，我有两个集合set1={1,2,4}set2={1,3}。5以下所有可能的有序数对是{1,2}、{1,3}、{1,4}、{2,3}、{2,4}和{3,4}。集合1中不同时存在的低于5的数的有序对是{1,3}、{2,3}和{3,4}。集合2中5以下缺失的有序对是{1,2}、{1,4}、{2,3}、{2,4}和{3,4}。两个集合中不同时存在的有序对是{2,3}和{3,4}。所以缺少的有序对的数量是2。

有谁能告诉我一种巧妙的方法来组织我的数据结构，以便更快地找到丢失的数据对？如果之前有人问过这个问题，我提前道歉。

更新：以下是关于我的数据集结构的一些信息。每组元素的数量从2到500000不等。元素的中位数约为10000。分布在10000左右达到峰值，并在两个方向上逐渐减少。100000组元素的并集接近1000000。

Answer 1

根据内存需求，您可以利用Set的顺序，巧妙地迭代值。就像下面的代码（未经测试）。您将迭代所有的集合，然后对每个集合迭代它们的值。对于这些值中的每一个，您将检查它们后面集合中的所有值。我们的复杂性降低到集合数乘以它们大小的平方。您可以使用各种方法来跟踪已找到/未找到的计数，但是使用集合应该没问题，因为插入只是O（log（n）），其中n不超过499999500000。理论上，使用集合映射（基于第一个值的映射）可能会稍微快一点，但在任何一种情况下，成本都是最小的。

long long numMissing(const std::array<std::set<int>, 100000>& sets){
    std::set<pair<int, int> > found;
    for (const auto& s : sets){
        for (const auto& m : s){
            const auto &n = m;
            for (n++; n != s.cend(); n++){
                found.emplace(m, n);
            }
        }
    }
    return 499999500000 - found.size();
}

Answer 2

首先，让我们解决一个更简单的任务：计算集合中不存在的元素的数量。这个任务可以用更简单的形式重新编写——你可以考虑一个包含所有数字的集合，而不是100000个集合。那么这个集合中不存在的元素数是x=1000000-len（集合）。现在，您可以使用这个数字x来计算组合的数量。有重复：x*x，无重复：x*（x-1）。所以我的答案的底线是把你们所有的数字放在一个大集合中，用它的长度，用组合数学找到组合的数量。

使现代化

所以上面我们有一个方法来找到组合中每个元素不在任何集合中的组合数。但是问题是找到每个组合不在任何集合中的组合数。

让我们先尝试解决更简单的问题：

• 你的集合里有所有的数字，没有一个丢失
• 每个数字都在一个集合中，没有跨集合的重复

你如何在这样的集合上构造这样的组合？您只需从不同的集合中选择两个元素，得到的组合不会出现在任何集合中。可以使用以下代码计算此类组合的数量（它接受集合的大小）：

int count_combinations(vector<int>& buckets) {
  int result = 0;
  for (int i=0; i < buckets.size(); ++i) {
    for (int j=i+1; j < buckets.size(); ++j) {
      result += buckets[i] * buckets[j];
    }
  }
  return result;
}

现在让我们想象一下，一些数字丢失了。然后，我们可以将这些缺失的数字添加到集合中（作为一个单独的集合）。但我们也需要考虑到，如果有n缺失的数字，那么就有n*（n-1）只使用这些缺失的数字构建的组合。因此，以下代码将生成帐户到缺失数字的组合总数：

int missing_numbers = upper_bound - all_numbers.size() - 1;
int missing_combinations = missing_numbers * (missing_numbers - 1);

return missing_combinations + count_combinations(sets, missing_numbers); 

现在让我们想象一下，我们在两个集合中有一个副本：{a，b，c}，{a，d}。他们会引入什么类型的错误？以下配对：{a，a}-重复，{a，d}-第二组中存在的组合。那么如何处理这样的重复？我们需要从所有集合中完全消除它们。即使是重复的单个实例，也会在某些集合中产生组合。因为我们可以从删除重复项的集合中选取任何元素，并生成这样的组合（在我的示例中，如果我们将a保留在第一个集合中，那么从第二个集合中选取d来生成{a，d}，如果我们将a保留在第二组中，那么从第一组中选择b或c，生成{a，b}和{a，c}）。因此，应删除副本。

使现代化

但是，我们不能简单地删除所有的重复，考虑这个反例：<代码> {a，b}< /COD> <代码> {a，c} <代码> {d} < /代码>。如果我们只是删除a，我们将获得{b}{c}{d}，并丢失关于不存在的组合的信息{a，d}。考虑另一个反例：<代码> {a，b} <代码> {a，b，c} <代码> <代码> {b，d} < /代码>。如果我们只是删除重复项，我们将获得{c}{d}，并丢失有关{a，d}的信息。

此外，我们不能简单地将这种逻辑应用于成对的集合，一个简单的数字反例

Answer 3

如果你正在寻找跨集合的组合，有一种方法可以有意义地压缩你的数据集，如frenzykryger的答案所示。然而，从你的例子中，你要寻找的是每个集合中可用组合的数量，这意味着每个集合包含不可约信息。此外，你也不能用组合数学简单地从每个集合中获得组合的数量；您最终希望在所有集合中消除重复数据，因此实际的组合很重要。

了解了所有这些，很难想到你能取得任何重大突破。假设你有i集合，每个集合中最多有k项。天真的方法是：

• 如果您的集合通常是密集的（即包含1到1,000,000之间的大部分数字），请用集合的补码替换它们
• 创建2元组的集合（使用集合结构，确保插入是幂等的）
• 对于每组O（i）：
  • 评估所有组合并插入组合集合：O（k选2）

  最糟糕的情况是，这种情况的复杂性不是很大，但假设在某些情况下，一个集合要么包含0到1000000之间的大多数数字，要么几乎没有，那么性能应该会有很大的提高。

  另一种方法是继续使用组合学来计算每个集合中的组合数量，然后使用一些有效的方法来查找集合中重复组合的数量。我不知道有这样的方法，但它可能存在。