序列序列的2组合的交集的并集

Question

如何在序列序列中找到2个或更多序列中出现的项集？

换句话说,我希望在传递的序列中至少有2个出现不同的值.

注意: 这不是所有序列的交叉,而是所有序列对的交叉的并集.

注2: 不包括序列与自身的对或2组合.那太傻了.

我自己做了一个尝试,

public static IEnumerable<T> UnionOfIntersects<T>(
                                  this IEnumerable<IEnumerable<T>> source)
{
    var pairs =
            from s1 in source
            from s2 in source
            select new { s1 , s2 };

    var intersects = pairs
        .Where(p => p.s1 != p.s2)
        .Select(p => p.s1.Intersect(p.s2));

    return intersects.SelectMany(i => i).Distinct();
}

但是我担心这可能是次优的,我认为它包括A,B和B对的交叉点,A似乎效率低下.我也认为可能有一种更有效的方法来复合集合,因为它们是迭代的.

---

我在下面包含一些示例输入和输出:

{ { 1, 1, 2, 3, 4, 5, 7 }, { 5, 6, 7 }, { 2, 6, 7, 9 } , { 4 } }

回报

{ 2, 4, 5, 6, 7 }

和

{ { 1, 2, 3} } or { {} } or { }

回报

{ }

我正在寻找可读性和潜在性能的最佳组合.

---

编辑

我已经对当前答案进行了一些初步测试,我的代码在这里.输出如下.

Original valid:True
DoomerOneLine valid:True
DoomerSqlLike valid:True
Svinja valid:True
Adricadar valid:True
Schmelter valid:True
Original 100000 iterations in 82ms
DoomerOneLine 100000 iterations in 58ms
DoomerSqlLike 100000 iterations in 82ms
Svinja 100000 iterations in 1039ms
Adricadar 100000 iterations in 879ms
Schmelter 100000 iterations in 9ms

目前,Tim Schmelter的答案看起来好像至少有一个数量级.

Answer 1

您可以尝试这种方法，它可能更有效，并且还允许指定最小交集计数和使用的比较器：

public static IEnumerable<T> UnionOfIntersects<T>(this IEnumerable<IEnumerable<T>> source 
    , int minIntersectionCount
    , IEqualityComparer<T> comparer = null)
{
    if (comparer == null) comparer = EqualityComparer<T>.Default;
    foreach (T item in source.SelectMany(s => s).Distinct(comparer))
    {
        int containedInHowManySequences = 0;
        foreach (IEnumerable<T> seq in source)
        {
            bool contained = seq.Contains(item, comparer);
            if (contained) containedInHowManySequences++;
            if (containedInHowManySequences == minIntersectionCount)
            {
                yield return item;
                break;
            }
        }
    }
}

一些解释的话：

• 它枚举所有序列中的所有唯一项。由于Distinct使用的是一组，所以这应该非常有效。如果所有序列中有许多重复项，这有助于加快速度。
• 内部循环仅查看每个序列是否包含唯一项。因此，它使用Enumerable.Contains一旦找到一项就停止执行（因此重复项不是问题）。
• 如果交叉计数达到最小交叉计数，则生成此项目并检查下一个（唯一）项目。