C#中如何使用LINQ按相同列组合分组并生成对应双集合列表

这个需求不是常规的固定键分组，本质是对Owner和PetCategory构成的二部关联图做边不重复的极大二部团覆盖：把所有关联记录拆成若干个分组，每个分组内的所有Owner都拥有分组内的所有PetCategory，所有分组覆盖全部原始记录且没有重复记录，和给出的期望输出规则完全匹配。

可以用贪心算法结合LINQ实现，步骤如下：

• 用哈希集合存储所有未分组的关联边
• 循环处理直到所有边都被分组：
  • 统计当前剩余边中每个Owner、每个PetCategory的关联度数（关联的边数）
  • 选度数最小的顶点（Owner或PetCategory均可）作为起点，扩展出当前能找到的极大完全二部团（即团内任意Owner和任意PetCategory都存在关联关系）
  • 把二部团覆盖的边从待处理集合中移除，将团映射为PetCategoriesOwners对象加入结果

前置类定义 #

public class PetCategoryOwner
{
    public string PetCategory { get; set; }
    public string Owner { get; set; }
}

public class PetCategoriesOwners
{
    public IEnumerable<string> PetCategories { get; set; }
    public IEnumerable<string> Owners { get; set; }
}

测试数据 #

var petCategoryOwner = new List<PetCategoryOwner>()
{
    new PetCategoryOwner { Owner = "Higa", PetCategory = "Terry"},
    new PetCategoryOwner { Owner = "Higa", PetCategory = "Charlotte"},
    new PetCategoryOwner { Owner = "Oliver", PetCategory = "Terry"},
    new PetCategoryOwner { Owner = "Oliver", PetCategory = "Charlotte"},
    new PetCategoryOwner { Owner = "Oliver", PetCategory = "Chausie"},
    new PetCategoryOwner { Owner = "Price", PetCategory = "Chausie"},
    new PetCategoryOwner { Owner = "Liam", PetCategory = "Terry"},
    new PetCategoryOwner { Owner = "Liam", PetCategory = "Chartreux"}
};

实现代码 #

说明：代码中用到的MinBy是.NET 6+内置方法，低版本可以替换为OrderBy(kv => kv.Value).First()

var remainingEdges = new HashSet<(string Owner, string Pet)>(
    petCategoryOwner.Select(x => (x.Owner, x.PetCategory))
);
var petCategoriesOwners = new List<PetCategoriesOwners>();

while (remainingEdges.Any())
{
    // 统计各顶点当前度数
    var ownerDegrees = remainingEdges
        .GroupBy(e => e.Owner)
        .ToDictionary(g => g.Key, g => g.Count());
    var petDegrees = remainingEdges
        .GroupBy(e => e.Pet)
        .ToDictionary(g => g.Key, g => g.Count());

    // 找度数最小的顶点作为扩展起点
    var minOwner = ownerDegrees.MinBy(kv => kv.Value);
    var minPet = petDegrees.MinBy(kv => kv.Value);

    HashSet<string> currentOwners, currentPets;
    if (minOwner.Value <= minPet.Value)
    {
        // 从Owner顶点扩展
        var startOwner = minOwner.Key;
        currentPets = remainingEdges
            .Where(e => e.Owner == startOwner)
            .Select(e => e.Pet)
            .ToHashSet();
        // 筛选出拥有当前所有Pet的Owner
        currentOwners = remainingEdges
            .Select(e => e.Owner)
            .Distinct()
            .Where(o => currentPets.All(p => remainingEdges.Contains((o, p))))
            .ToHashSet();
        // 再筛选出被当前所有Owner共同拥有的Pet，确保是极大团
        currentPets = remainingEdges
            .Select(e => e.Pet)
            .Distinct()
            .Where(p => currentOwners.All(o => remainingEdges.Contains((o, p))))
            .ToHashSet();
    }
    else
    {
        // 从Pet顶点扩展
        var startPet = minPet.Key;
        currentOwners = remainingEdges
            .Where(e => e.Pet == startPet)
            .Select(e => e.Owner)
            .ToHashSet();
        // 筛选出被当前所有Owner共同拥有的Pet
        currentPets = remainingEdges
            .Select(e => e.Pet)
            .Distinct()
            .Where(p => currentOwners.All(o => remainingEdges.Contains((o, p))))
            .ToHashSet();
        // 再筛选出拥有当前所有Pet的Owner，确保是极大团
        currentOwners = remainingEdges
            .Select(e => e.Owner)
            .Distinct()
            .Where(o => currentPets.All(p => remainingEdges.Contains((o, p))))
            .ToHashSet();
    }

    // 移除已分组的边
    foreach (var owner in currentOwners)
    {
        foreach (var pet in currentPets)
        {
            remainingEdges.Remove((owner, pet));
        }
    }

    // 加入结果集
    petCategoriesOwners.Add(new PetCategoriesOwners
    {
        PetCategories = currentPets,
        Owners = currentOwners
    });
}

结果说明 #

运行代码后得到的petCategoriesOwners包含3个元素，和期望结构完全一致，仅分组顺序可能不同，可按需排序：

1. 分组1：PetCategories = ["Chausie"], Owners = ["Oliver", "Price"]
2. 分组2：PetCategories = ["Terry", "Chartreux"], Owners = ["Liam"]
3. 分组3：PetCategories = ["Terry", "Charlotte"], Owners = ["Higa", "Oliver"]

内容的提问来源于stack exchange，提问作者Ming Tsai