如何在C#中合并两个Enumerable并保留源序列相对顺序？

这个问题的核心是将两个序列的偏序约束转化为唯一的全序序列，本质是拓扑排序的典型应用。以下是具体实现方案：

核心逻辑 #

1. 提取两个序列的所有唯一元素，作为待排序的集合。
2. 用有向图构建元素间的先后约束：如果序列中A在B之前，就添加一条A→B的有向边，表示A必须排在B前面。
3. 通过拓扑排序验证约束是否一致（无环），同时检查是否存在唯一的全序结果：
   • 若图中有环（比如A必须在B前，同时B必须在A前），返回空序列。
   • 若排序过程中出现多个可选的起始元素，说明存在多种合法全序，返回空序列。
   • 否则返回唯一的拓扑排序结果。

C# 实现代码 #

using System;
using System.Collections.Generic;
using System.Linq;

public static class EnumerableMerger
{
    public static IEnumerable<T> MergePreservingOrder<T>(IEnumerable<T> first, IEnumerable<T> second) where T : IEquatable<T>
    {
        var allElements = first.Concat(second).Distinct().ToList();
        if (!allElements.Any())
            return Enumerable.Empty<T>();

        // 构建有向图：key为节点，value为该节点的后继节点集合
        var graph = new Dictionary<T, HashSet<T>>();
        // 记录每个节点的入度（前置节点数量）
        var inDegree = new Dictionary<T, int>();

        // 初始化图与入度字典
        foreach (var element in allElements)
        {
            graph[element] = new HashSet<T>();
            inDegree[element] = 0;
        }

        // 为单个序列添加相邻元素的约束边
        void AddSequenceConstraints(IEnumerable<T> sequence)
        {
            var elements = sequence.ToList();
            for (int i = 0; i < elements.Count - 1; i++)
            {
                var current = elements[i];
                var nextElement = elements[i + 1];
                if (current.Equals(nextElement))
                    continue; // 跳过连续重复元素，不生成约束

                // 避免重复添加同一条边，防止入度重复累加
                if (!graph[current].Contains(nextElement))
                {
                    graph[current].Add(nextElement);
                    inDegree[nextElement]++;
                }
            }
        }

        // 为两个输入序列分别添加约束
        AddSequenceConstraints(first);
        AddSequenceConstraints(second);

        // 用Kahn算法进行拓扑排序，同时检测环与唯一性
        var queue = new Queue<T>();
        var result = new List<T>();
        bool hasMultipleValidOrders = false;

        // 初始化队列：加入所有入度为0的节点
        foreach (var node in inDegree.Where(kvp => kvp.Value == 0).Select(kvp => kvp.Key))
        {
            queue.Enqueue(node);
        }

        while (queue.Count > 0)
        {
            // 若当前有多个入度为0的节点，说明存在多种合法全序
            if (queue.Count > 1)
            {
                hasMultipleValidOrders = true;
                break;
            }

            var currentNode = queue.Dequeue();
            result.Add(currentNode);

            // 更新后继节点的入度
            foreach (var neighbor in graph[currentNode])
            {
                inDegree[neighbor]--;
                if (inDegree[neighbor] == 0)
                {
                    queue.Enqueue(neighbor);
                }
            }
        }

        // 结果长度不等于总元素数 → 图中有环（约束矛盾）
        if (result.Count != allElements.Count)
        {
            return Enumerable.Empty<T>();
        }

        // 存在多种合法全序 → 无法确定唯一顺序
        if (hasMultipleValidOrders)
        {
            return Enumerable.Empty<T>();
        }

        return result;
    }
}

// 测试用例
class Program
{
    static void Main()
    {
        // 正常合并场景
        var seq1 = new List<string> { "foxtrot", "uniform", "kilo" };
        var seq2 = new List<string> { "uniform", "charlie", "kilo" };
        Console.WriteLine("正常合并结果：" + string.Join(", ", EnumerableMerger.MergePreservingOrder(seq1, seq2)));

        // 顺序矛盾场景
        var seq3 = new List<string> { "foxtrot", "uniform" };
        var seq4 = new List<string> { "uniform", "foxtrot" };
        var conflictResult = EnumerableMerger.MergePreservingOrder(seq3, seq4);
        Console.WriteLine("矛盾场景结果：" + (conflictResult.Any() ? string.Join(", ", conflictResult) : "空序列"));

        // 无法确定顺序场景
        var seq5 = new List<string> { "foxtrot", "charlie" };
        var seq6 = new List<string> { "uniform", "kilo" };
        var ambiguousResult = EnumerableMerger.MergePreservingOrder(seq5, seq6);
        Console.WriteLine("无法确定顺序场景结果：" + (ambiguousResult.Any() ? string.Join(", ", ambiguousResult) : "空序列"));
    }
}

代码说明 #

• 泛型兼容：通过IEquatable<T>确保任意可比较类型的元素都能被处理。
• 去重与约束去重：自动合并重复元素，同时避免重复添加相同的约束边，防止入度计算错误。
• 边界处理：支持空序列、单序列输入，以及序列内连续重复元素的情况。
• 正确性验证：通过结果长度判断是否存在环，通过队列元素数量判断是否存在多种合法全序。

内容的提问来源于stack exchange，提问作者wexman