时间戳

首页 > 解决方案 > 将列表组合在一起

c# - 将列表组合在一起

问题描述

我有一个对象列表（Session），它们可能通过彼此链接。一个属性 ( 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
    }
}

我尝试遵循 Blindy 的回答：

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);
        }
    }
}

标签： c#linq

解决方案

你需要两个数据结构：

  1. ADictionary<int, Session>快速将 id 映射到会话
  2. AHashSet<Session>举行会议仍有待处理

你先把所有东西都推入集合，然后当集合不为空时，你取出一个并用它开始一个新的集群，然后递归地对其父母和孩子以及集群的父母和孩子做同样的事情。

集群也是一个集合，不允许重复。

编辑：一个快速而肮脏的实现是这样的（复杂性大约是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

线上展示

推荐阅读