带组的复杂 LINQ 排序

Question

我试图根据以下（简化的）规则对项目列表进行排序：

我将每个项目都具有以下属性：

 Id (int), 
 ParentId (int?), 
 Name (string)

ParentID 是一个到 Id 的自连接外键。如果一个项目有 ParentId，那么父项目也将存在于列表中。

我需要对列表进行排序，以便所有具有父级的项目都立即出现在其父级之后。然后所有项目将按名称排序。

因此，如果我有以下内容：

 Id: 1, ParentId: null, Name: Pi
 Id: 2, ParentId: null, Name: Gamma
 Id: 11, ParentId: 1, Name: Charlie
 Id: 12, ParentId: 1, Name: Beta
 Id: 21, ParentId: 2, Name: Alpha
 Id: 22, ParentId: 2, Name: Omega

那么我希望它们按如下方式排序：

ID：2、21、22、1、12、11

目前我能想到的最好办法是先按名称排序，然后按 ParentId 分组，如下所示：

var sortedItems = itemsToSort.OrderBy(x=> x.Name).GroupBy(x=> x.ParentId);

我的起始计划如下：（在非功能状态代码）

var finalCollection = new List<Item>

var parentGroup = sortedItems.Where(si => si.Key == null);

foreach(parent in parentGroup)
{
   finalCollection.Add(parent);
   foreach(child in sortedItems.Where(si => si.Key == parent.Id)
   {
      finalCollection.Add(child);
   }
}

但是，parentGroup 不是

 IEnumerable<Item> 

，所以这不起作用。

我觉得有一种更简单、更简洁的方法可以实现这一目标，但目前它却让我困惑——任何人都可以帮忙吗？

Answer 1

如果您只有两个级别，您可以这样做：

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => new[] { x }.Concat(lookup[x.Id]));

最初，项目按名称排序，确保稍后将它们分成组时它们保持排序。

然后创建一个查找表，允许通过 ParentId 进行查找。然后，使用 SelectMany 将通过 null ParentId 标识的父级与其子级连接起来，并使用查找表来查找子级。将父级插入到子级之前以获得所需的序列。

如果你想解决两层以上的一般情况，你需要使用递归。这是一种递归获取节点子树的方法：

IEnumerable<Item> GetSubtreeForParent(Item parent, ILookup<Int32?, Item> lookup) {
  yield return parent;
  foreach (var child in lookup[parent.Id])
    foreach (var descendant in GetSubtreeForParent(child, lookup))
      yield return descendant;
}

代码几乎与上面的简单情况相同：

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
var parents = lookup[null];
var sortedItems = parents.SelectMany(x => GetSubtreeForParent(x, lookup));

通过使用递归 lambda，您甚至可以“内联”完成所有操作：

var lookup = itemsToSort.OrderBy(x => x.Name).ToLookup(x => x.ParentId, x => x);
// Declare Func to allow recursion.
Func<Int32?, IEnumerable<Item>> getSubTreeForParent = null;
getSubTreeForParent =
  id => lookup[id].SelectMany(x => new[] { x }.Concat(getSubTreeForParent(x.Id)));
var sortedItems = getSubTreeForParent(null);

Answer 2

据我了解您的问题，您希望按父名称（如果是父名称）然后按子名称（如果是子名称）对结果进行排序，但您希望所有子名称都出现在列表中各自的父名称之后。

这应该可以解决问题：

更新以解决@Martin Liversage提到的问题。

var query = from item in itemsToSort
            let parent = itemsToSort.Where(i => i.Id == item.ParentId).FirstOrDefault()
            //get the name of the item's parent, or the item itself if it is a parent
            let parentName = (parent != null) ? parent.Name : item.Name
            //get the name of the child (use null if the item isn't a child)
            let childName = (parent != null) ? item.Name : null
            orderby parentName, childName
            select item;

var finalCollection = query.ToList();

这是输出：

Answer 3

这可以通过以下方式实现：

list.Select(i => 
      new {Parent=list.Where(x => x.Id == i.ParentId).FirstOrDefault(), Item = i})
    .OrderBy(i => i.Parent == null ? i.Item.Name : i.Parent.Name + i.Item.Name)
    .Select(i => i.Item)

实例：http://rextester.com/rundotnet?code=WMEZ40628

输出为：

2
21
22
1
12
11

Answer 4

我会选择 DoctaJonez 的 答案 2 级。

它可以扩展到 n 层，如下所示：

Func<int?,Item> lookup = id => list.Where(i => i.Id == id).FirstOrDefault();

Func<Item,string> makeSortString = null;
makeSortString = i => i.ParentId == null ? i.Name : makeSortString(lookup(i.ParentId)) + i.Name;

list.OrderBy(makeSortString).ToList();

Answer 5

这

var parentGroup = sortedItems.Where(si => si.Key == null).ToList()

将使 parentGroup IEnumerable 。

你会在顶层失去懒惰，但我认为由于上下文，这很好。

Answer 6

这个怎么样？

var lookup = items.ToLookup(x => x.ParentId);

Func<int?, IEnumerable<Item>> f =  null;
f = ni =>
    from a in lookup[ni].OrderBy(x => x.Name)
    from b in (new [] { a }).Concat(f(a.Id))
    select b;

然后要获取排序列表，请执行以下操作：

var sorted = f(null);

简单。 :-)