将多个重叠集划分为非重叠集

Question

我有多个具有重叠元素的集合。

e1, e2, e3, e4
e7,e9,e10
e1,e4
e2,e7
e3,e9
e10,e11,e12
e11,e12

我想划分上述集合，使它们不重叠并遵循块中的现有边界。所以我期待的输出是

e1, e4
e2
e3
e7
e9
e10
e11, e12

我可以编写什么算法/函数来执行此操作？

Answer 1

我将首先计算每个元素的"参与签名"。例如，元素 e1 参与集合 1 和 3，因此其签名应为 1010000。具有相同签名的元素应位于同一最终集中。

---

更新：这是这个想法的实现，使用BigInteger类作为参与签名。

using System.Numerics;
public static IEnumerable<IEnumerable<T>> GetDistinctGroupedByOrigin<T>(
IEnumerable<IEnumerable<T>> source)
{
return source
.SelectMany((s, i) => s.Select(e => (Element: e, Index: i)))
.GroupBy(e => e.Element)
.Select(g => (Element: g.Key, Signature: g.Aggregate(
BigInteger.Zero, (acc, e) => acc | (BigInteger.One << e.Index))))
.GroupBy(e => e.Signature, e => e.Element);
}

使用示例：

var source = new string[][]
{
new string[] { "e1", "e2", "e3", "e4" },
new string[] { "e7", "e9", "e10" },
new string[] { "e1", "e4" },
new string[] { "e2", "e7" },
new string[] { "e3", "e9" },
new string[] { "e10", "e11", "e12" },
new string[] { "e11", "e12" },
};
foreach (var set in GetDistinctGroupedByOrigin(source))
{
Console.WriteLine(String.Join(", ", set));
}

输出：

E1， E4
E2 E3
E7
E9
E10 E11
， E12