Объединить два перечисляемых числа, сохраняя порядок, определенный любым источником

Я отредактировал свой ответ, чтобы проверить наличие дубликатов и противоречий. Теперь это должно работать во всех случаях. Проверка каждого из них заключалась в том, чтобы убедиться, что ни исходные списки, ни возвращенный список не содержат дубликатов. (Если бы было противоречие, то в отсортированном возвращаемом списке были бы дубликаты)

class Program {
    static void Main(string[] args) {
        IEnumerable<string> l1 = new List<string> { "uniform", "charlie", "kilo" };
        IEnumerable<string> l2 = new List<string> { "kilo", "uniform", "charlie" };
        try {
            IEnumerable<string> result = Merge(l1, l2);
            foreach (string s in result) {
                Console.WriteLine(s);
            }
        }
        catch (InvalidOperationException e) {
            Console.WriteLine(e.Message);
        }
        Console.ReadKey();
    }

    public static IEnumerable<T> Merge<T> (IEnumerable<T> list1, IEnumerable<T> list2) {
        if ((list1.Distinct().Count() != list1.Count()) || (list2.Distinct().Count() != list2.Count()) ) {
            throw new InvalidOperationException("Couldn't merge.  One or both lists contained duplicates.");
        }
        
        if ((list1.Count() == 0)) {
            return list2;
        }
        if ((list2.Count() == 0)) {
            return list1;
        }
        List<T> newList = new List<T>();       
        bool matchfound = false;
        for(int i = 0; i< list1.Count(); i++) {
            for (int j = 0; j < list2.Count(); j++) {
                if (list1.ElementAt(i).Equals(list2.ElementAt(j))) {
                    matchfound = true;
                    newList.AddRange(Merge(list1.Take(i), list2.Take(j)));
                    newList.Add(list1.ElementAt(i));
                    newList.AddRange(Merge(list1.Skip(i + 1), list2.Skip(j + 1)));
                    break;
                }
            }
            if (matchfound) {
                break;
            }
        }
        if (!matchfound) {
            throw new InvalidOperationException("Could not merge");
        }
        if (newList.Distinct().Count() != newList.Count()) {
            throw new InvalidOperationException("Couldn't merge.  Contradiction in lists.");

        }
        return newList;
    }

}

Обзор

Первое, что пришло мне в голову при чтении задачи, было: «Это похоже на задачу с графом». В этом случае элементы ваших перечислимых элементов являются узлами, а порядок перечисляемых элементов образует ребра.

Например, рассмотрим «ABCD» как одно из входных перечислимых чисел. Мы можем преобразовать это в такой график:

A --> B --> C --> D

Если вторым входом является «B-X-Y-C», он сам по себе формирует график:

B --> X --> Y --> C

Теперь мы можем представить проблему в виде объединенного графа, в котором повторяющиеся узлы складываются в один, объединяя входящие и исходящие ребра.

A --> B -----------> C --> D 
      |              ^       
      |              |       
      +-> X --> Y ---+       

Исходя из этого, мы можем построить «объединенный порядок», идя слева направо, добавляя узел в порядок только в том случае, если все узлы, ведущие к нему, уже присутствуют в порядке. В этом примере объединенный порядок: «A-B-X-Y-C-D».

Как отметил в комментарии пользователь «dbc», это соответствует определению топологической сортировки, упорядочивания узлов графа, при котором каждый узел появляется только после своих зависимостей.

Более того, используя конструкцию графа, мы теперь можем формально определить «противоречие» порядка как цикл в графе. Если узел «I» указывает на «J», а «J» указывает на «I» (как на входах «I-J» и «J-I»), вы можете представить, как в результирующем графе есть узлы «I» и «J». ", указывая друг на друга в цикле.

Мы также должны рассмотреть ситуацию, когда существует несколько точек «входа» и «выхода», например. с учетом входных данных «M-N-O-P» и «Z-N-X-Y», который образует X-образный граф, где «M» и «Z» указывают на «N», а «N» разветвляется на две цепочки «OP» и «XY». Это можно решить, разрешив первому вводу иметь приоритет и последовательно объединяя отдельные элементы в равных ветвях. Это сформирует порядок: «M-Z-N-O-X-P-Y». Альтернативно, мы могли бы объединить сами ветки последовательно: «M-Z-N-O-P-X-Y». Обе являются допустимыми топологическими сортировками. На момент написания этой статьи первоначальный вопрос не касался того, какой порядок предпочтителен.

Наконец, у нас есть еще один случай, когда два графа не пересекаются, например. заданы входы «ABC» и «XYZ». Эти две цепочки не имеют общих элементов. Согласно задаче, это должно привести к сбою и возврату пустого заказа. Это можно рассматривать как отдельный случай, возможно, путем сканирования перечислимых элементов на наличие хотя бы одного общего узла перед выполнением какой-либо другой работы.

Разработка алгоритма

На высоком уровне мы можем разбить проблему на две части: построение объединенного графа и формирование порядка. Существует несколько алгоритмов топологической сортировки, поэтому структура данных, в которой хранится граф, будет зависеть от того, какой алгоритм выбран.

В этом случае я буду использовать Алгоритм Кана, который имеет очень чистый шаблон псевдокода, расположенный в Википедии. Алгоритм Кана требует двух вещей: графа, отслеживающего входящие и исходящие ребра, и списка «начальных узлов» (узлов без входящих ребер).

Структура данных для графа может представлять собой модифицированный список смежности, в котором каждый узел хранится в качестве ключа в словаре, а значение для каждого представляет собой список непосредственно соседних узлов. Хотя типичный список смежности хранит только исходящие ребра, мы также можем отслеживать входящие ребра, добавляя второй список для каждого ключа. Это будет выглядеть так:

"B" : {
    "nodes that point into this one": [
        "A"
    ],
    "nodes that this one points to" : [ 
        "C"
    ]
},
...

Чтобы избежать необходимости сканирования графа после построения «начальных узлов», мы можем просто отслеживать потенциальные начальные узлы во время построения графа и удалять их как кандидатов, если они когда-либо получат входящее ребро. Учитывая контекст проблемы, мы знаем, что единственные потенциальные начальные узлы — это элементы в начале перечислимого — все, что происходит дальше, обязательно имеет узел, указывающий на него.

После этого давайте разработаем код для построения графа и списка «начальных узлов». Концептуально нам просто нужно перебрать каждое перечисляемое, добавить каждый элемент в качестве узла и нарисовать границу между ним и предыдущим элементом. Если узел в графе уже существует, мы добавляем ребро к существующему узлу вместо того, чтобы добавлять его дубликат.

(Я написал свой код на Python для простоты тестирования, преобразовать его в C# должно быть довольно просто.) Обновлено: версия C# указана в конце.

def ConstructGraph(*args):
    graph = {}
    start_points = []
    for enumerable in args:
        AttachToGraph(graph, enumerable, start_points)
    return graph, start_points

        
def AttachToGraph(graph, enumerable, start_points):
    seen_nodes = set()
    previous_node = None

    ## Tentatively add the first element as a start point.
    if enumerable[0] not in graph and enumerable[0] not in start_points:
        start_points.append(enumerable[0])

    for current_node in enumerable:
        ## Handle the obvious error case where a node is repeated in the same enumerable (e.g. "A, B, A")
        if current_node in seen_nodes:
            raise f"Found duplicate in enumerable."

        ## Add the element as a node.
        if current_node not in graph:
            graph[current_node] = {"outgoing": [], "incoming": []}

        ## Draw the edge between the current node and the previous one.
        if previous_node != None:
            graph[previous_node]["outgoing"].append(current_node)
            graph[current_node]["incoming"].append(previous_node)

            ## If we find a start point with an incoming edge, it's not a start point.
            if current_node in start_points:
                start_points.remove(current_node)

        seen_nodes.add(current_node)
        previous_node = current_node

Например, вызов ConstructGraph("ACFG", "BCDEF") сформирует следующий граф: Граф с узлами A и B, указывающими на C, который указывает на F и D. Узел D указывает на E, который указывает на F. Узел F указывает на G.

Ожидаемый порядок после завершения топологической сортировки будет (очень удобно): «ABCDEFG».

Вот моя реализация алгоритма Кана на Python с использованием псевдокода из Википедии в качестве шаблона. Я назвал переменные с именами переменных псевдокода в качестве префикса, а также более понятным именем.

def Kahn(graph, start_points):
    S_queue = start_points[:] ## We could re-use start_points, but let's clone it for clarity.
    L_ordering = []
    while len(S_queue) > 0:
        N_node = S_queue.pop(0)
        L_ordering.append(N_node)

        ## Clone the edge list to avoid problems when iterating
        destinations = graph[N_node]["outgoing"][:] 

        for M_destination in destinations:
            ## Remove the edge both ways.
            graph[N_node]["outgoing"].remove(M_destination)
            graph[M_destination]["incoming"].remove(N_node)

            ## Once all the dependencies are in the ordering, enqueue the destination node.
            if len(graph[M_destination]["incoming"]) == 0:
                S_queue.append(M_destination)

    ## Check for cycles.
    for N_node in graph:
        if len(graph[N_node]["outgoing"]) > 0 or len(graph[N_node]["incoming"]) > 0:
            return []

    return L_ordering

Объединив функции, мы можем сделать следующее:

graph, start_points = ConstructGraph("ACFG", "BCDEF")
print(Kahn(graph, start_points))
## prints "ABCDEFG"

Этот код не обрабатывает непересекающиеся перечислимые элементы, поскольку эту проблему можно решить заранее, реализовав проверку на то, имеют ли данные перечислимые элементы общий элемент или нет.

Обновлено: Версия С#

(Возможно, я откусил больше, чем могу переварить, пытаясь сделать его универсальным; этот код предполагает, что TObject не является сложным ссылочным типом. Пожалуйста, измените код в соответствии со своими потребностями.)

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

public static class Merge
{
    public static List<TObject> MergeLists<TObject>(params IEnumerable<TObject>[] enumerables)
    {
        (Dictionary<TObject, Dictionary<string, List<TObject>>> graph, List<TObject> startPoints) = ConstructGraph(enumerables);
        return (graph == null) ? new List<TObject>() : Kahn(graph, startPoints);
    }


    private static (Dictionary<TObject, Dictionary<string, List<TObject>>> Graph, List<TObject> StartPoints) ConstructGraph<TObject>(params IEnumerable<TObject>[] args)
    {
        Dictionary<TObject, Dictionary<string, List<TObject>>> graph = new Dictionary<TObject, Dictionary<string, List<TObject>>>();
        List<TObject> startPoints = new List<TObject>();

        foreach (IEnumerable<TObject> enumerable in args)
        {
            try
            {
                AttachToGraph(ref graph, enumerable, ref startPoints);
            }
            catch // I advise defining a custom exception type, or alternatively pre-sanitizing the enumerables.
            {
                graph = null;
                break;
            }
        }
        return (graph, startPoints);
    }

    private static void AttachToGraph<TObject>(
        ref Dictionary<TObject, Dictionary<string, List<TObject>>> graph,
        IEnumerable<TObject> enumerable,
        ref List<TObject> startPoints)
    {
        HashSet<TObject> seenNodes = new HashSet<TObject>();
        TObject previousNode = default;
        bool isStartOfEnumerable = true;

        if (!graph.ContainsKey(enumerable.ElementAt(0)) && !startPoints.Contains(enumerable.ElementAt(0)))
        {
            startPoints.Add(enumerable.ElementAt(0));
        }

        foreach (TObject currentNode in enumerable)
        {
            // Sanity check the enumerable.
            if (seenNodes.Contains(currentNode))
            {
                throw new Exception("Found an obviously invalid IEnumerable."); // If you're going with this, define a custom exception.
            }

            if (!graph.ContainsKey(currentNode))
            {
                graph.Add(currentNode, new Dictionary<string, List<TObject>>{
                    {"outgoing", new List<TObject>()},
                    {"incoming", new List<TObject>()}
                });
            }

            if (!isStartOfEnumerable)
            {
                graph[previousNode]["outgoing"].Add(currentNode);
                graph[currentNode]["incoming"].Add(previousNode);

                if (startPoints.Contains(currentNode))
                {
                    startPoints.Remove(currentNode);
                }
            }

            seenNodes.Add(currentNode);
            previousNode = currentNode;

            // Update flag.
            if (isStartOfEnumerable)
            {
                isStartOfEnumerable = false;
            }
        }
    }

    private static List<TObject> Kahn<TObject>(
        Dictionary<TObject, Dictionary<string, List<TObject>>> graph,
        List<TObject> startPoints)
    {
        // Note that this creates a shallow copy, update this to deep-copy if needed.
        Queue<TObject> queue = new Queue<TObject>(startPoints);
        List<TObject> ordering = new List<TObject>();

        while (queue.Count > 0)
        {
            TObject node = queue.Dequeue();

            ordering.Add(node);

            // Modify to deep-copy if TObject is a complex reference type.
            List<TObject> destinations = new List<TObject>(graph[node]["outgoing"]);

            foreach (TObject destination in destinations)
            {
                graph[node]["outgoing"].Remove(destination);
                graph[destination]["incoming"].Remove(node);

                if (graph[destination]["incoming"].Count == 0)
                {
                    queue.Enqueue(destination);
                }
            }
        }

        foreach (TObject node in graph.Keys)
        {
            if (graph[node]["outgoing"].Count > 0 || graph[node]["incoming"].Count > 0)
            {
                return new List<TObject>();
            }
        }

        return ordering;
    }
}

Используйте так:

List<string> list1 = new List<string> { "A", "B", "D", "F" };
List<string> list2 = new List<string> { "B", "C", "D", "E", "F" };
List<string> result = Merge.MergeLists(list1, list2);

// 'result' has the order "ABCDEF".