Входные данные: массив элементов и частичный порядок подмножества этих элементов, рассматриваемый как набор ограничений.
Вывод: массив (или любая упорядоченная последовательность), удовлетворяющий частичному порядку.
Проблема: как можно эффективно изменить порядок? Количество введенных инверсий (или перестановок) по сравнению с исходной входной последовательностью должно быть как можно меньше. Обратите внимание, что частичный порядок может быть определен для любого количества элементов (некоторые элементы могут не входить в него).
Контекст: возникает из ситуации при уменьшении пересечения двухслойного графа: после фазы сокращения пересечения я хочу изменить порядок некоторых узлов (таким образом, частичный порядок может содержать только небольшое подмножество) .
В общем, у меня была идея немного ослабить это и решить задачу только для элементов, входящих в частичный порядок (хотя я думаю, что это могло привести к неоптимальным результатам). Таким образом, если у меня есть последовательность A B C D E, а частичный порядок содержит только A, B и E, то C и D останутся на одном месте. Это чем-то напоминает мне оценку Кемени, но я еще не мог превратить это в алгоритм.
Просто чтобы быть уверенным: я не ищу топологическую сортировку. Это, вероятно, приведет к гораздо большему количеству инверсий, чем требуется.
Редактировать 1:
- Изменена формулировка (последовательность в массив).
- Объем дополнительного пространства для решения задачи может быть сколь угодно (ну, полиномиально ограниченным) большим. Конечно, чем меньше, тем лучше :) Таким образом, что-то вроде O(ArrayLen*ArrayLen) самое большее было бы фантастическим.
- Почему минимальное количество свопов или инверсий: поскольку эта процедура является частью сокращения пересечений, порядок входного массива (надеюсь) близок к оптимальному с точки зрения пересечений ребер со вторым слоем узлов. Тогда каждый дополнительный обмен или инверсия, вероятно, снова приведет к пересечению ребер. Но в процессе вычисления вывода количество сделанных перестановок или движений не очень важно (хотя, опять же, что-то линейное или квадратичное было бы круто), так как важно только качество вывода. Прямо сейчас я требую, чтобы ограничения были в общем порядке и проверяли только узлы этого порядка, поэтому решение становится тривиальным. Но ограничения частичного порядка были бы более гибкими.
