按没有共同元素分组？

Question

我有一个 class 例如：

public class SomeClass {
    public HashSet<int> Items;
}

我想将 SomeClass 与其他不共享任何项目的 SomeClass 分组。
示例：假设我们有 3 个 SomeClass (S1-S4) 例如：
S1:
• 项目：1、2、6
S2:
• 项目：3、4、5
S3:
• 项目：1
S4:
• 项目：1、5
S5:
• 项目：8、9

在那种情况下，组应该如下：
G1: S1, S2, S5
G2：S3
G3：S4

理想情况下，项目应放置在成员最少的组中，以便所有组的大小相对相同。

如何实现？

Answer 1

无法在 Linq 中定义此分组。 Linq 中的 GroupBy 需要“相等”的定义，并且该定义必须是可传递的，这意味着如果 A=B 和 B=C，则 A=C 必须为真。您的定义不是可传递的，如您的输入 S1=S2 和 S2=S3，但 S1!=S3.

您可以做的是遍历所有项目，根据需要创建新组，并向组添加项目以保持您所说的较小尺寸。

因此您可以从 S1 开始，查找包含 1 的其他项目，然后将它们放入新的组中（在本例中为 S3 和 S4） .然后查找包含 2 的项目，将它们放入在步骤 1 中创建的组中，交替组。

按照这个逻辑你应该得到：

G1: S1, S2
G2: S3, S5
G3: S4

但是，同样，这不能在 Linq 中完成 - 您必须自己编写循环和分组逻辑代码。

Answer 2

答案仅供娱乐，提供了一个甚至可以被认为是 LINQ 的语句转换你把“聚合”算作 LINQ (LINQPad-ready):

void Main()
{
    var list = new[] {
        new SomeClass("s1", 1,2,6),
        new SomeClass("s2", 3,4,5), 
        new SomeClass("s3", 1),
        new SomeClass("s4", 1,5), 
        new SomeClass ("s5", 8,9)
    };
    
    var r = list.Aggregate(new List<IEnumerable<SomeClass>>().AsEnumerable(),
        (result, cur) => result
            // groups that should be copied
            .Where(w => w != result.FirstOrDefault(
                  x => x.SelectMany(c => c.Items).Intersect(cur.Items).Count() == 0))
            .Concat(Enumerable.Repeat(
                // adding to existing one
                (result.FirstOrDefault(
                   x => x.SelectMany(c => c.Items).Intersect(cur.Items).Count() == 0) ??
                // adding to new one
                new List<SomeClass>())
                    // add current item to existing/new group
                    .Concat(Enumerable.Repeat(cur, 1)),
                1))
            );
                                 
    r.Dump();
}

// Define other methods and classes here
public class SomeClass
{
    public SomeClass(string name, params int[] items)
    {
        Name = name;
        Items= new HashSet<int>(items);
    }
    public string Name;
    public HashSet<int> Items;
}

Sort-of 说明：

每次迭代

将组列表分成两半 - 第一个合适的组添加当前项目，其余组使用相同的条件。
对于其余的组（.Where 选择除了潜在的第一个合适的组之外的所有组）只是让它们不受影响地移动到下一个迭代
对于合适的群组，有两种选择 - 我们实际上有一个群组要添加，或者没有这样的群组，我们需要创建一个新群组。为了统一代码，我们只使用 result.FirstOrDefault(...) ?? new List<...>() - 这给出了一个列表来添加新项目，该项目要么包含以前迭代的项目，要么包含新项目。
将当前项目添加到合适的组 - .Concat 需要我们用 Enumerable.Repeat(cur,1).
将“要复制的组列表”与“具有当前元素的单个组列表”连接起来。

如果您尝试自己破解相同的代码，请注意：

如果您只勾选“无交集”，则很容易将“当前”组添加到多个现有组。我们必须只考虑第一个合适的组才能使代码正常工作
随后，如果您尝试使用某种不会在第一次匹配时停止的“相交”过滤器，则很容易丢失现有内容。
将顶级 Concat 视为“根据 true/false 将列表分成两部分”并合并修改后的结果。
创建新组很容易得到 wrong/miss 一共

按没有共同元素分组？

Group by NOT having element in common?

c#

linq

sorting

algorithm

group-by