c# - 一系列序列的 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 { }

返回

{ }

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

---

编辑

我对当前答案进行了一些初步测试，my code is here .输出如下。

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's answer性能至少提高一个数量级。

Answer 1

// init sequences
var sequences = new int[][]
    { 
        new int[] { 1, 2, 3, 4, 5, 7 },
        new int[] { 5, 6, 7 },
        new int[] { 2, 6, 7, 9 },
        new int[] { 4 }
    };

单线方式:

var result = sequences
    .SelectMany(e => e.Distinct())
    .GroupBy(e => e)
    .Where(e => e.Count() > 1)
    .Select(e => e.Key);

// result is { 2 4 5 7 6 }

类似 SQL 的方式(带排序):

var result = (
          from e in sequences.SelectMany(e => e.Distinct())
          group e by e into g
          where g.Count() > 1
          orderby g.Key
          select g.Key);

// result is { 2 4 5 6 7 }

可能是最快的代码(但不可读)，复杂度 O(N):

var dic = new Dictionary<int, int>();
var subHash = new HashSet<int>();
int length = array.Length;
for (int i = 0; i < length; i++)
{
    subHash.Clear();
    int subLength = array[i].Length;
    for (int j = 0; j < subLength; j++)
    {
        int n = array[i][j];
        if (!subHash.Contains(n))
        {
            int counter;
            if (dic.TryGetValue(n, out counter))
            {
                // duplicate
                dic[n] = counter + 1;
            }
            else
            {
                // first occurance
                dic[n] = 1;
            }
        }
        else
        {
            // exclude duplucate in sub array
            subHash.Add(n);
        }
    }
}