2

問題

unorderedList<Item>があり、それぞれが一意の ID によってリスト内のItem別のものを指すことができます。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

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 に答える