时间戳

首页 > 解决方案 > 从列表中获取最长的子类别链

c# - 从列表中获取最长的子类别链

问题描述

我的应用程序中有一个数据结构，看起来有点像这样（这只是一个小例子）。

public class Category
{
    public string Name { get; set; }
    public List<SubCategory> subCategories { get; set; }
}

public class SubCategory
{
    public int order { get; set; }
    public string Name { get; set; }
}

使用这种结构，我创建了一个这样的列表：

class Program
{
    static void Main(string[] args)
    {
        var duplicateCategory = new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "App",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    },
                    new SubCategory
                    {
                        Name = "Sidepanel",
                        order = 3
                    }
                }
        };

        var duplicateCategory2 = new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "Website",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    }
                }
        };

        var categories = new List<Category>
        {
            //APP
            duplicateCategory,
            duplicateCategory,
            new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "App",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    }
                }
        },
            //WEBSITE
            duplicateCategory2,
            duplicateCategory2,
            new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "Website",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    },
                    new SubCategory
                    {
                        Name = "Sidepanel",
                        order = 3
                    }
                }
        }
    };
    }
}

现在从这个列表中我需要删除重复项，我已经使用 linq 的“不同”实现了这一点。

然而，一个额外的要求是我需要从这个列表中获取相同子类别的最长链。因此，鉴于上面的列表，我只想返回这两个对象：

new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "App",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    },
                    new SubCategory
                    {
                        Name = "Sidepanel",
                        order = 3
                    }
                }
        };

和

new Category
        {
            Name = "E-platform",
            subCategories = new List<SubCategory> {
                    new SubCategory
                    {
                        Name = "Website",
                        order = 1
                    },
                    new SubCategory
                    {
                        Name = "Layout",
                        order = 2
                    },
                    new SubCategory
                    {
                        Name = "Sidepanel",
                        order = 3
                    }
                }
        }

因此，您可以看到它从列表中删除了“E-platform -> 1. App -> 2. layout -> 3.Sidepanel”中的 1 个，以避免重复（我已经弄清楚了）。

它还删除了“E-platform -> 1. App -> 2. layout”，因为“E-platform -> 1. App -> 2. layout -> 3.Sidepanel”有一个额外的级别（我不能弄清楚）

请记住，可能会更深一层以上，我只想要最深的类别而不丢弃其他不同的类别。

获得此列表的任何帮助都会非常有帮助！如果您需要更多信息，请与我们联系。

标签： c#algorithm.net-core

解决方案

目前尚不完全清楚您要实施哪些规则，但希望以下内容会有所帮助：

var cleanCategoryList = categories
    .Distinct()
    // I'm guessing you only want to compare subcategories if the top-category
    // Names are the same. So... group them:
    .GroupBy(c => c.Name)
    .SelectMany(group =>
    {
        var candidates = group
            // Create tuple containing the category itself as well as a set of
            // the names of the sub categories
            .Select(c =>
            (
                c,
                c.SubCategories
                    .Select(sc => sc.Name)
                    .ToHashSet()
            ))
            .OrderByDescending(c => c.Item2.Count); // Important - see below

        var catsWithUniqSubCats = new List<(Category, HashSet<string>)>();
        foreach (var tuple in candidates)
        {
            // Since we sort by descending Count of the set of sub cat. names
            // we only need to compare each tuple with those already picked for
            // the resulting list
            if (!catsWithUniqSubCats.Any(c => tuple.Item2.IsSubsetOf(c.Item2)))
                // The tuple's category's sub categories are not a subset of
                // any other list of sub categories, so we add it to the result
                catsWithUniqSubCats.Add(tuple);
        }
        return catsWithUniqSubCats.Select(tup => tup.Item1);
    });

请参阅.Net fiddle进行测试。

推荐阅读