用于查找元素列表中重复细分的交集的有效算法

Question

为清晰起见进行编辑：我正在寻找C#中最有效(最好是优雅(的方法来找到同一集合的各个细分的n向交集。详细信息如下。

---

1. 我有一个元素列表。为了简单起见，假设它是1-100的整数
2. 该列表已被划分为多个组，因此所有元素都存在于一个组中。例如，第1组
   • 第一组：1,5-8,52-73
   • 第2组：2-4,38-51
   • 第3组：9-37,84-100
   • 第4组：74-83
3. 步骤#2已经重复了许多次(即，该列表中有许多不同的划分(。例如：第2组
   • 第一组：1-27,59-80,99-100
   • 第2组：28-31,81-98
   • 第3组：32-58
4. 我想"合并"(这可能有一个更好的术语(这些除法，这样，如果任何两个元素在任何一个除法中都是分开的，那么它们在最终结果中就会分开。换句话说：只有那些在所有划分中结合在一起的元素才是最终结果。例如，对于上述两个分区(D=分区，g=组(：
   • 第1组(D1G1 x D2G2(:1,5-8,59-73
   • 第2组(D1G1 x D2G3(:52-58
   • 第3组(D1G2 x D2G1(：2-4
   • 第4组(D1G2 x D2G3(:38-51
   • 第5组(D1G3 x D2G1(：9-27,99-100
   • 第6组(D1G3 x D2G2(：28-31，84-98
   • 第7组(D1G3 x D2G3(:32-37
   • 第8组(D1G4 x D2G1(:74-80
   • 第9组(D1G4 x D2G2(:81-83

我不在乎最终结果中组的顺序。我只是在寻找最高效、最干净的解决方案。

目前，我能想到的唯一方法是：

public IEnumerable<IEnumerable<int>> MergeDivisions(IEnumerable<IEnumerable<IEnumerable<int>>> divisions)
{
var currentMerge = divisions.First();
foreach (var division in divisions.Skip(1))
{
var nextMerge = new List<List<int>>();
foreach (var currentMergeGroup in currentMerge)
{
foreach (var group in division)
{
var nextMergeGroup = currentMergeGroup.Intersect(group);
if (nextMergeGroup.Any())
nextMerge.Add(nextMergeGroup.ToList());
}
}
currentMerge = nextMerge;
}
return currentMerge;
}

Answer 1

提示：

如果我是对的，你只是试图产生群**的成对交集，其中一个群可以被描述为区间[b,e)*的列表。我假设区间是从左到右排序的。由于所有间隔都由两个边界描述，因此可以使用平面列表。

例如

{1, 2, 5, 9, 52, 74} ∩ {28, 32, 71, 99}

现在想象一个标准的列表合并过程(如Mergesort(，它将导致

{1, 2, 5, 9, 28, 32, 52, 71, 74, 99}

对于该列表中的每个绑定，您可以准确地判断哪些间隔包含它和以下元素。

{1, 2, 5, 9, 28, 32, 52, 71, 74, 99}
1  -  1  -  1   -   1   3   2   -

(3表示1+2(。

现在很容易看出，两组中的元素都是[71, 74)，而仅第一组中的是[1, 2)、[5, 9)、[28, 32)、[52, 71)。

*使用最后一个索引加一更方便。

**我不确定我是否理解您是如何定义合并的，但我想上面的技术可能很有用。