2

问题

我有一个 unordered List<Item>，其中每个都Item可以通过唯一 ID 指向Item列表中的另一个。

我想对列表进行排序，以便每个列表Item后面跟着Item它指向的。

在此处输入图像描述

初始化列表

public class Item {
    public string ID {get;set;}
    public string nextID {get;set;}
}

void Main()
{

    var items = new List<Item>();

    items.Add(new Item  { ID = "X", nextID = "" });
    items.Add(new Item  { ID = "A", nextID = "D" });
    items.Add(new Item  { ID = "C", nextID = "B" });
    items.Add(new Item  { ID = "E", nextID = "" });
    items.Add(new Item  { ID = "B", nextID = "A" });    
    items.Add(new Item  { ID = "D", nextID = "" });         

    SortItems(items);

    // should result in Items with IDs in this order: ["X","E","C","B","A","D"]

}
4

2 回答 2

2

TSort()使用这个答案中的拓扑排序函数，我编写了以下函数来排序我的规范：

public List<Item> sortItems(List<Item> items) {

    // perform a topological sort
    var sortedItems = 
        items.TSort(item => items.Where(o=>item.ID == o.nextID || item.nextID == ""))
        .ToList();

    // this next code moves the unpointed items to top of list

    // find items that are not pointed to, and do not point to any other item
    var soloItems= 
        sortedItems.Where(o => !sortedItems.Where(p => p.nextID == o.ID).Any() && o.nextID == "").ToList();

    // reverse the soloItems list so they
    // to appear in the same order in which 
    // they were found in unsorted list
    soloItems.Reverse();    

    // move the soloItems from the bottom of sortedItems to the top of sortedItems
    sortedItems.RemoveAll(o => soloItems.Contains(o));
    sortedItems.InsertRange(0,soloItems);

    return sortedItems;     

}
于 2013-08-16T17:09:44.027 回答
0

有趣的问题。起初我想知道是否可以使用带有一些选择器代表的简单 Linq 查询构造，但这很快就会变得混乱。

下面的简单 linq 构造可以帮助您完成部分工作，但实际上还需要使用和传播计数以及原始输入顺序。

// Simple Linq, but just not good enough
// Need to also propagate original input order and count the number of siblings
Func<IEnumerable<Item>, Item, IEnumerable<Item>> SelectSuccessors = (set, item) => set.Where(i => i.ID == item.nextID);
Func<IEnumerable<Item>, IEnumerable<Item>, IEnumerable<Item>> Flatten = null;
Flatten = (set, sibblingPool) => set
    .SelectMany(i => new[] { i }.Concat(Flatten(SelectSuccessors(sibblingPool.Except(set), i), sibblingPool.Except(set))));
var unparented = items.Where(i => !items.Any(n => n.nextID == i.ID));
foreach (var item in Flatten(unparented, items))
    Console.WriteLine(item.ID);

它的结果是 ["X", "C", "B", "A", "D", "E"]

一种非常不同的构造类型是在自递归数据结构中真正捕捉到这个问题的递归结构：

public class ItemHierarchy : Tuple<Item, int, List<ItemHierarchy>>
{
    public static List<ItemHierarchy> BuildHierarchy(IEnumerable<Item> items)
    {
        var inputOrderNumbered = items.Select((item, order) => Tuple.Create(item, order));
        var roots = inputOrderNumbered.Where(i => !items.Any(n => n.nextID == i.Item1.ID));
        return roots.Select(r => BuildFor(r.Item1, r.Item2, inputOrderNumbered.Except(roots))).ToList();
    }

    public Item Item 
    { 
        get { return this.Item1; } 
    }
    public int OriginalInputOrder
    {
        get { return this.Item2; }
    }
    public int NumberOfDescendents
    {
        get { return this.Item3.Count + this.Item3.Sum(i => i.NumberOfDescendents); }
    }
    public IEnumerable<Item> Flattened
    {
        get { return new[] { this.Item }.Concat(Descendents); }
    }
    public List<ItemHierarchy> DescendentHierarchy
    {
        get { return this.Item3; }
    }
    public IEnumerable<Item> Descendents
    {
        get { return this.Item3.SelectMany(i => new [] { i.Item }.Concat(i.Descendents)); }
    }
    public IEnumerable<Item> Leafs
    {
        get
        {
            if (NumberOfDescendents == 0)
                return new[] { this.Item };
            else
                return DescendentHierarchy.SelectMany(d => d.Leafs);
        }
    }
    protected ItemHierarchy(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> descendents, IEnumerable<Tuple<Item, int>> remaining)
        : base(item, originalOrder, descendents.Select(d => BuildFor(d.Item1, d.Item2, remaining)).ToList())
    {
    }

    private static ItemHierarchy BuildFor(Item item, int originalOrder, IEnumerable<Tuple<Item, int>> numberedSiblings)
    {
        var descendents = numberedSiblings.Where(s => s.Item1.ID == item.nextID);
        return new ItemHierarchy(item, originalOrder, descendents, numberedSiblings.Except(descendents));
    }
}

然后可以用来解决您提出的问题：

// This works quite well.
// As a bonus it preserves the original input information 
// and offers a navigatable/queryable hierarchy.
var hierarchy = ItemHierarchy.BuildHierarchy(items);
foreach (var item in hierarchy.OrderBy(r => r.NumberOfDescendents).ThenBy(r => r.OriginalInputOrder).SelectMany(r => r.Flattened))
    Console.WriteLine(item.ID);
于 2013-08-17T01:33:06.523 回答