Алгоритм - объединить несколько списков, в результате чего уникальный список и сохраняя порядок

Question

Я хочу объединить несколько списков товаров в один список, сохранив общие требования к заказу. i.e.:

1: A C E
2: D E
3: B A D

result: B A C D E

выше, начиная со списка 1, у нас есть ACE, тогда мы знаем, что D должен предшествовать E, а из списка 3 мы знаем, что B должен предшествовать A, а D должен идти после B и A.

Если имеются противоречивые заказы, следует использовать первый заказ. т.е.

1: A C E
2: B D E
3: F D B

result: A C F B D E 

3 конфликтует с 2 (B D против D B), поэтому будут использоваться требования для 2.

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

Это разрабатывается с использованием VB.Net, поэтому было бы неплохо использовать решение LINQy (или любое решение .Net) - в противном случае было бы неплохо использовать указатели для подхода.

Редактировать: отредактировано, чтобы сделать пример 2 более понятным (изменение в последнюю минуту сделало его недействительным)

Answer 1

Ключевое слово, которое вас, вероятно, интересует, - "Топологическая сортировка". Основанное на этом решение будет выглядеть следующим образом:

• Создать пустой ориентированный граф.
• Обрабатывайте последовательности по порядку, для каждых двух последовательных элементов X, Y в последовательности добавляйте ребро X-> Y к графику, если только это не сформирует цикл.
• Выполнить топологическую сортировку по вершинам графа. Полученная последовательность должна удовлетворять вашим требованиям.