Блог

У меня есть список из n отсортированных списков с m элементами (строками) в каждом. Эти элементы происходят из списка с определенным порядком, который я не знаю. Я знаю, что все подсписки поддерживают глобальный порядок элемента. Списки не являются непересекающимися. Объединение списков является подмножеством исходного списка.

Теперь я изо всех сил пытаюсь найти алгоритм, который эффективно объединил бы их обратно в список (списков) с максимальной точностью сортировки.

Есть ли решение для такой проблемы?

Я использую Java, вот несколько примеров кода:

 List<List<String>> elements = new ArrayList<>();

elements.add(Lists.newArrayList("A","D","F"));
elements.add(Lists.newArrayList("B","D","E"));
elements.add(Lists.newArrayList("A","B","G"));
elements.add(Lists.newArrayList("C","D","H"));

// the required method
List<List<String>> sorted = sortElements(elements);

/* expeced output:
 * [["A"],["B"],["C"],["D"],["G","F","E","H"]]
 */
  

Вы ищете топологическую сортировку.

Ваши исходные списки представляют собой направленные дуги графа (A-> D, D-> F и т. Д.)

P.S. Специальный вид топологической сортировки для явного разделения узлов по уровням называется в русской литературе «Алгоритмом демокрона», но мне не удалось найти правильное описание на английском языке (найдены ссылки на статьи по рисованию плоских графов)

Пример его работы: