Заказать список родителей / детей

Question

У меня проблема с сортировкой списка по родительскому дочернему элементу.

Вот код, доступный на C # dotnetfiddle.net

Это модель объекта сечения:

public class Section
{
    public int Id { get; set; } //dont care
    public int SectionID { get; set; } //the actual ID I use
    public int SectionRowId { get; set; } //something else
    public string Name { get; set; } //just display
    public int ParentID { get; set; } //parent id connection
}

Существует список разделов, которые могут быть в любом смешанном порядке.

 Random R = new Random().Next(1000);

 new Section() { Id = 9,    Name = R.Next(1000).ToString(), SectionID = 900,     SectionRowId = 1, ParentID = 3     }   
,new Section() { Id = 5,    Name = R.Next(1000).ToString(), SectionID = 137,     SectionRowId = 4, ParentID = 0     }   
,new Section() { Id = 8,    Name = R.Next(1000).ToString(), SectionID = 3,       SectionRowId = 3, ParentID = 137   } 
,new Section() { Id = 1,    Name = R.Next(1000).ToString(), SectionID = 888,     SectionRowId = 1, ParentID = 0     }   
,new Section() { Id = 3,    Name = R.Next(1000).ToString(), SectionID = 137,     SectionRowId = 2, ParentID = 0     }   
,new Section() { Id = 4,    Name = R.Next(1000).ToString(), SectionID = 137,     SectionRowId = 3, ParentID = 888   } 
,new Section() { Id = 6,    Name = R.Next(1000).ToString(), SectionID = 3,       SectionRowId = 1, ParentID = 0     }   
,new Section() { Id = 7,    Name = R.Next(1000).ToString(), SectionID = 3,       SectionRowId = 2, ParentID = 0     }   
,new Section() { Id = 2,    Name = R.Next(1000).ToString(), SectionID = 137,     SectionRowId = 1, ParentID = 0     }   
,new Section() { Id = 10,   Name = R.Next(1000).ToString(), SectionID = 11,      SectionRowId = 1, ParentID = 900   } 
,new Section() { Id = 11,   Name = R.Next(1000).ToString(), SectionID = 8,       SectionRowId = 1, ParentID = 137   } 
,new Section() { Id = 12,   Name = R.Next(1000).ToString(), SectionID = 8,       SectionRowId = 2, ParentID = 0     }

Ожидаемый результат:

    Id    SectionId / SectionRowId (Parent SectionID)
    01) - [ 888 / 001 ]
    02) - [ 137 / 001 ]
    03) - [ 137 / 002 ]
    04) - [ 137 / 003 ] <- 888      // is available before ^^
    05) - [ 137 / 004 ]
    06) - [ 003 / 001 ]
    07) - [ 003 / 002 ]
    08) - [ 003 / 003 ] <- 137      // is available before ^^
    09) - [ 900 / 001 ] <- 003      // is available before ^^
    10) - [ 011 / 001 ] <- 900      // is available before ^^
    11) - [ 008 / 001 ] <- 137      // is available before ^^
    12) - [ 008 / 002 ]

Легенда о выше ожидаемом результате:

Example 04) - [ 137 / 003 ] <- 888      // is available before ^^

888 является родителем 137 и доступен до этого.

01) - [ 888 / 001 ]

Если бы это было ниже этого, тогда это не было бы хорошо.

EDIT:

Пожалуйста, посмотрите: https://dotnetfiddle.net/FCZF5X#&togetherjs=aIbJ64NwJv Я добавил это, чтобы все было случайным и проверки для этого. Так что это может быть более понятно.

Из нового случайного кода это должно выглядеть так:

Items count: 12
Final result is: True


            [ ORIGINAL LIST ]               |                [ SORTED LIST ]                   
-----------------------------------------------------------------------------------------------
  ID    |    Section / Row     |   Parent   |     ID    |    Section / Row     |   Parent      

025116) - [ 004337 / 084754 ] <-- 011973    |    008134) - [ 011973 / 018572 ]
028628) - [ 006663 / 045806 ] <-- 011973    |    083009) - [ 011973 / 013626 ]
099494) - [ 004337 / 075769 ] <-- 006663    |    080161) - [ 011973 / 023149 ]
051824) - [ 004337 / 086590 ]               |    059540) - [ 011973 / 045751 ]
008134) - [ 011973 / 045751 ]               |    078203) - [ 011973 / 061979 ]
002017) - [ 005938 / 073913 ] <-- 011973    |    025800) - [ 006663 / 045806 ]
083009) - [ 011973 / 023149 ]               |    028628) - [ 006663 / 082944 ] <-- 011973
037537) - [ 005938 / 038984 ] <-- 004337    |    051824) - [ 004337 / 075769 ]
025800) - [ 006663 / 082944 ]               |    099494) - [ 004337 / 084754 ] <-- 006663
080161) - [ 011973 / 018572 ]               |    025116) - [ 004337 / 086590 ] <-- 011973
059540) - [ 011973 / 061979 ]               |    037537) - [ 005938 / 038984 ] <-- 004337
078203) - [ 011973 / 013626 ]               |    002017) - [ 005938 / 073913 ] <-- 011973

Сводка отсортированного списка выше ^^:

• ID = не важно
• Секция = должна быть сгруппирована
• Ряд = должен быть заказан по возрастанию
• Parent = Если есть, группа родительских разделов должна быть выше этой группы.

Answer 1

Вот как я решил это сейчас ... если кому-то еще понадобится в будущем.

private static List<Section> SortTheList(List<Section> messyList)
    {
        List<Section> newList = new List<Section>();
        List<Section> outList = new List<Section>();
        newList.AddRange(messyList);

        int[] sectionIDs = newList.Select(x => x.SectionID).Distinct().ToArray();
        int[] no = GetOrder(newList).ToArray();
        foreach (int sectionID in no)
        {
            IEnumerable<Section> thisSectionGroup = newList.Where(x => x.SectionID == sectionID);
            thisSectionGroup = thisSectionGroup.OrderBy(x => x.SectionRowId).ThenBy(x => x.ParentID);
            outList.AddRange(thisSectionGroup);
        }

        return outList;
    }

    private static List<int> GetOrder(List<Section> allSections)
    {

        Dictionary<int, int> orderList = new Dictionary<int, int>();
        int[] sectionIDs = allSections.Select(x => x.SectionID).Distinct().ToArray();
        foreach (int sectionID in sectionIDs) { orderList.Add(sectionID, 0); }
        foreach (int sectionID in sectionIDs)
        {
            int[] parentIDs = allSections.Where(x => x.SectionID == sectionID && x.ParentID > 0).Select(x => x.ParentID).ToArray();
            foreach (int parentID in parentIDs)
            {
                IncParents(allSections, parentID, ref orderList);
            }
        }
        return orderList.OrderByDescending(x => x.Value).Select(x => x.Key).ToList();
    }

    private static void IncParents(List<Section> allSections, int parentID, ref Dictionary<int, int> orderList, int incLevel = 1)
    {
        orderList[parentID] = orderList[parentID] + incLevel;
        int[] parentIDs = allSections.Where(x => x.SectionID == parentID && x.ParentID > 0).Select(x => x.ParentID).ToArray();
        foreach (int subParentID in parentIDs)
        {
            IncParents(allSections, subParentID, ref orderList, (incLevel + 1));
        }
    }

https://dotnetfiddle.net/1VNqSB

Не стесняйтесь улучшать его или делать его более элегантным:)