Skuteczne wstawianie do listy przy minimalnej liczbie inwersji

Załóżmy dwie listy porównywalnych pozycji: u i s. Niech INV (u) będzie liczbą inwersji wu.

Szukam wydajnego algorytmu do wstawiania elementów s do u przy minimalnym wzroście INV (u).

Zasadniczo chciałbym wstawić obiekty do listy, zachowując ją „tak posortowaną, jak to możliwe”, zachowując kolejność pierwszej listy.

Przykład:

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))

Jak widać, nie ma unikalnego optymalnego rozwiązania.

Byłbym zadowolony z każdego rodzaju pomysłów lub wskazówek.

To jest rozwinięcie odpowiedzi Trevore'a. Jest za długi, aby zmieścić się w komentarzu i zawiera dowody swojego rozwiązania (a przynajmniej tego, jak je rozumiem).

Możesz pokazać, że w każdym optymalnym rozwiązaniu elementy pojawią się w porządku. $s$Jeśli nie, załóżmy i pojawią się w odwrotnej kolejności w optymalnym rozwiązaniu. Niech σ 1 będzie liczbą elementów między s 1 i s 2, które są mniejsze niż s 1, a β 1 będzie liczbą tych, które są większe niż s 1 . Zdefiniuj σ 2 i β 2 podobnie dla s 2 . Zauważ, że σ 1$s_1 < s_2$$\sigma_1$$s_1$$s_2$$s_1$$\beta_1$$s_1$$\sigma_2$$\beta_2$$s_2$ i β 2 ≤ β 1 . Zamiana s 1 i s 2 zmieni liczbę inwersji o - β 1 + β 2 - σ 2 + σ 1 - 1, co najwyżej -1.$\sigma_1 \leq \sigma_2$$\beta_2 \leq \beta_1$$s_1$$s_2$$-\beta_1 + \beta_2 - \sigma_2 + \sigma_1 - 1$

Nietrudno zauważyć, że elementy można wstawiać niezależnie. $s$Ponieważ wydają się uporządkowane, elementy „nie czują” swojej obecności. Oznacza to, że pary elementów z s nie wpływają na liczbę inwersji. Aby to zrobić, wstaw medianę s optymalnie w czasie liniowym. Następnie rekurencyjnie wstaw elementy s mniejsze niż mediana po lewej stronie mediany i elementy większe niż mediana po prawej stronie.$s$$s$$s$$s$

Niech mediana zostanie wstawiona w pozycję , czas jej działania jest zgodny, T ( | s | , | u | ) = T ( | s | / 2 , | u | - k ) + T ( | s | / 2 , k ) + | u | + | s | , liniowy | s $k$$T(|s|, |u|) = T(|s| / 2, |u| - k) + T(|s| / 2, k) + |u| + |s|$$|s|$czynnik służy do znalezienia mediany i przetasowania elementów . Indukcję łatwo wykazać, że T ( | s | , | u | ) = O ( | s | log | s | + | u | log | s | ) .$s$$T(|s|, |u|) = O(|s| \log |s| + |u| \log |s|)$

$|s|$$u$$s$$|u|$$s$$u$

Ok, oto moje rozwiązanie:

Spostrzeżenie (które mniej więcej udowodniłem) jest takie, że optymalnym rozwiązaniem zawsze będzie takie, w którym s jest posortowane rosnąco. To powoduje powstanie algorytmu O ((| u | + | s |) * log (| s |)).

Aby znaleźć optymalne rozwiązanie dla pojedynczego elementu, zrób tak, jak powiedziałem w moim komentarzu: Weź jeden element z s, porównaj go z każdym elementem wu od lewej do prawej, przyrost licznika jest inwersją i przenieś wcześniej obliczoną liczbę. Następnie przeglądaj listę od prawej do lewej z tym samym elementem, zwiększając liczbę dla każdej pozycji.

To jest O (| u |).

Sortuj s.

Dla środkowego elementu s w pozycji m: Znajdź najlepszą pozycję bw (stosując metodę z góry).

Podziel si na m iu na b, a następnie rekurencyjnie przywołaj lewą i prawą część, łącząc wyniki z m we właściwej kolejności.

Zatrzymaj się, gdy tylko u lub s będą puste.