Эффективная вставка в список с минимальным количеством инверсий

Предположим, два списка сопоставимых предметов: и и с. Пусть INV (u) будет числом инверсий в u.

Я ищу эффективный алгоритм для вставки элементов s в вас с минимальным увеличением INV (u).

По сути, я хотел бы вставлять объекты в список, сохраняя его «как можно более отсортированным», сохраняя порядок первого списка.

Пример:

u = [4,6,2,9,7]
INV(u) = 3 ((4, 2), (6, 2) and (9, 7)

s = [8,3,10]

one optimal solution u' = [3, 4, 6, 2, 8, 9, 7, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (8,7))

different optimal solution u' = [3, 4, 6, 2, 9, 7, 8, 10]
INV(u') = 5 ((4, 2), (7, 2) and (9, 7) + (3,2), (9,8))

Как видите, единственного оптимального решения не существует.

Я был бы рад за любые идеи или направления для изучения.

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

Вы можете показать, что в любом оптимальном решении элементы будут выглядеть упорядоченными. $s$Если нет, предположим, что и они появляются в обратном порядке в оптимальном решении. Пусть σ 1 будет количеством элементов между s 1 и s 2 , которые меньше s 1, а β 1 будет количеством элементов, которые больше s 1 . Определите σ 2 и β 2 аналогично для s 2 . Обратите внимание, что σ 1$s_1 < s_2$$\sigma_1$$s_1$$s_2$$s_1$$\beta_1$$s_1$$\sigma_2$$\beta_2$$s_2$ и β 2 ≤ β 1 . Замена s 1 и s 2 изменит количество инверсий на - β 1 + β 2 - σ 2 + σ 1 - 1, что не более -1.$\sigma_1 \leq \sigma_2$$\beta_2 \leq \beta_1$$s_1$$s_2$$-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$

Нетрудно видеть, что элементы могут быть вставлены независимо. $s$Поскольку они кажутся упорядоченными, элементы не «чувствуют» присутствие друг друга. То есть пары элементов из s не влияют на счет инверсии. Для этого оптимально вставьте медиану s в линейное время. Затем, рекурсивно, вставьте элементы s меньше медианы слева от медианы и элементы больше медианы справа.$s$$s$$s$$s$

Пусть медиана будет вставлена ​​в позицию , время выполнения которой удовлетворяет, T ( | s | , | u | ) = T ( | s | / 2 , | u | - k ) + T ( | s | / 2 , k ) + | ты | + | с | линейный | с $k$$T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$$|s|$фактор для нахождения медианы и перемешивания элементов . По индукции легко показать, что T ( | s | , | u | ) = O ( | s | log | s | + | u | log | s | ) .$s$$T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$

Обратите внимание, что зависимость от здесь оптимально. Поскольку решение проблемы с пустым u эквивалентно сортировке s с использованием только сравнений. Зависимость от | ты | также оптимально, поскольку задача для одноэлементного списка s и списка u должна требовать линейной работы.$|s|$$u$$s$$|u|$$s$$u$

Хорошо, вот мое решение:

Наблюдение (которое я более или менее доказал) состоит в том, что оптимальным решением всегда будет решение, в котором s отсортировано по возрастанию. Это приводит к алгоритму O ((| u | + | s |) * log (| s |)).

Чтобы найти оптимальное решение для одного элемента, сделайте, как я уже сказал в моем комментарии: возьмите один элемент из s, сравните его с каждым элементом в u слева направо, увеличьте счетчик в обратном порядке и перенесите ранее вычисленное число. Затем пройдитесь по списку справа налево с тем же элементом, увеличивая количество для каждой позиции.

Это O (| u |).

Сортировка

Для среднего элемента s в позиции m: найдите лучшую позицию b в u (используя метод сверху).

Разделите s на m и u на b и рекурсивно вызовите с левой и правой частями, объединяя результаты с m в правильном порядке.

Остановитесь, как только вы или s опустеете.