Группировка списков <T>

Question

У меня есть список объектов (Session), которые потенциально связаны друг с другом через. a property (ParentSessionId)

public class Session
{
    public int Id;
    public int? ParentSessionId;
}

Как я могу «сгруппировать» список всех сеансов с их «дочерними» сеансами в «коллекции»?

Думаю, я мог бы Я слишком усложняю свою попытку в коде:

List<Session> shiftSessions = new List<Session>();
var cluster;

foreach (var s in shiftSessions)
{
    List<Session> familySessions = new List<Session>();
    List<Session> singleSessions = new List<Session>();

    if (s.ParentSessionId == null)
    {
        if (shiftSessions.Any(x => x.ParentSessionId == s.Id))
        {
            familySessions.Add(s);
            familySessions.AddRange(shiftSessions.Where(x => x.ParentSessionId == s.Id));
            cluster.Add(familySessions); //if cluster doesn't contain familySessions
        }
        else
        {
            singleSessions.Add(s);
            cluster.Add(singleSessions); //if cluster doesn't contain singleSessions
        }
    }
    else
    {
        familySessions.Add(s);
        familySessions.AddRange(shiftSessions.Where(x => x.Id == (int)s.ParentSessionId));
        cluster.Add(familySessions); //if cluster doesn't contain familySessions
    }
}

Моя попытка после ответа Блинди:

List<Session> shiftSessions = new List<Session>();
Dictionary<int, Session> dict = new Dictionary<int, Session>();
HashSet<Session> sessions = new HashSet<Session>();

foreach (var s in shiftSessions)
{
    dict.Add(s.Id, s);
    sessions.Add(s);
}

foreach (var s in sessions)
{
    List<Session> familySessions = new List<Session>();
    List<Session> singleSessions = new List<Session>();

    if (s.ParentSessionId == null)
    {
        if (shiftSessions.Any(x => x.ParentSessionId == s.Id))
        {
            familySessions.Add(s);
            familySessions.AddRange(shiftSessions.Where(x => x.ParentSessionId == s.Id));
            cluster.Add(s.Id, s); //if cluster doesn't contain familySessions

            sessions.Remove(s);
            foreach (var parent in shiftSessions.Where(x => x.ParentSessionId == s.Id))
            {
                sessions.Remove(parent);
            }
        }
        else
        {
            singleSessions.Add(s);
            cluster.Add(singleSessions); //if cluster doesn't contain singleSessions

            res.Remove(s);
        }
    }
    else
    {
        familySessions.Add(s);
        familySessions.AddRange(shiftSessions.Where(x => x.Id == (int)s.ParentSessionId));
        cluster.Add(s.Id, s); //if cluster doesn't contain familySessions

        sessions.Remove(s);
        foreach (var child in shiftSessions.Where(x => x.Id == (int)s.ParentSessionId))
        {
            sessions.Remove(child);
        }
    }
}

Answer 1

Создайте новый тип, содержащий Session с его дочерними элементами:

public class SessionWithChildren {
    public Session session;
    public List<SessionWithChildren> children = new List<SessionWithChildren>();
}

Создайте карту от Id до SessionWithChildren:

var sessionLookup = sessions.ToDictionary(s => s.Id, s => new SessionWithChildren() { session = s });

Сгруппировать все сеансы вместе по родителю:

var children = sessionLookup.GroupBy(skvp => skvp.Value.session.ParentSessionId, skvp => skvp.Value);

Теперь вы можете go через детей, у которых есть родители, и назначить их правильному родителю:

foreach (var childgroup in children.Where(sg => sg.Key.HasValue)) {
    foreach (var child in childgroup) {
        sessionLookup[child.session.ParentSessionId.Value].children.Add(child);
    }
}

Наконец, сеансы без родителей сформируйте root вашего дерева:

var ans = children.First(sg => !sg.Key.HasValue).ToList();

Answer 2

Вам нужны две структуры данных:

1. A Dictionary<int, Session> для быстрого сопоставления идентификаторов сеансам
2. A HashSet<Session> для удержания сеансов, которые все еще обрабатываются

Вы помещаете все в набор sh, затем, пока набор не пуст, вы берете один и начинаете с ним новый кластер, а затем рекурсивно делаете то же самое для его родителей и потомков, а также для кластера. родители и дети.

Кластер также является набором, чтобы не допускать дублирования.

Изменить: быстрая и грязная реализация выглядит примерно так (сложность примерно O(n logn):

    struct T
    {
        public int Id, ParentId;

        public T(int id, int parentId) { Id = id; ParentId = parentId; }

        public override bool Equals(object obj) => obj is T t && Id == t.Id && ParentId == t.ParentId;
        public override int GetHashCode() => HashCode.Combine(Id, ParentId);

        public static bool operator ==(T left, T right) => left.Equals(right);
        public static bool operator !=(T left, T right) => !(left == right);
    }

    static void Main(string[] _)
    {
        var input = new[] { new T(0, -1), new T(1, -1), new T(2, 0), new T(3, 2), new T(4, 2), new T(5, 1) };

        var inputSet = input.ToHashSet();
        var parentLookup = input.ToDictionary(w => w.Id, w => w.ParentId);
        var results = new List<List<T>>();

        while (inputSet.Any())
        {
            var val = inputSet.FirstOrDefault(w => w.ParentId == -1);
            if (val.ParentId == 0) break;           // done

            // remove from the active inputs and add to the result cluster
            inputSet.Remove(val);
            List<T> cluster;
            results.Add(cluster = new List<T> { val });
            var clusterIds = new HashSet<int> { val.Id };

            // add all children for the cluster elements until no more are available
            while (true)
            {
                var children = inputSet.Where(w => clusterIds.Contains(w.ParentId)).ToList();
                if (!children.Any()) break;

                children.ForEach(w => { inputSet.Remove(w); cluster.Add(w); clusterIds.Add(w.Id); });
            }
        }

        results.ForEach(r => Console.WriteLine($"{string.Join(", ", r.Select(w => w.Id))}"));
    }

Результат:

0, 2, 3, 4
1, 5

Онлайн-витрина