Skuteczne wstawianie do listy przy minimalnej liczbie inwersji

15

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.

trevore
źródło
Myśl do przemyślenia: Naiwne podejście brzmiałoby: weź jeden element ze s, porównaj go z każdym elementem uw od lewej do prawej, zwiększaj, jeśli jest to odwrócenie 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. Działa to w O (| s | * | u |) ze spacją = O (| u |)
trevore 15.04.16
1
Sprawdzanie wszystkich maksymalnych rosnących podciągów może gdzieś prowadzić.
Raphael

Odpowiedzi:

2

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. sJeś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 σ 1s1<s2σ1s1s2s1β1s1σ2β2s2 i β 2β 1 . Zamiana s 1 i s 2 zmieni liczbę inwersji o - β 1 + β 2 - σ 2 + σ 1 - 1, co najwyżej -1.σ1σ2)β2)β1s1s2)-β1+β2)-σ2)+σ1-1

Nietrudno zauważyć, że elementy można wstawiać niezależnie. sPonieważ 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.ssss

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 |kT.(|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 | ) .sT.(|s|,|u|)=O(|s|log|s|+|u|log|s|)

|s|us|u|su

aelguindy
źródło
Dziękuję za opracowanie. To właśnie miałem na myśli rozwiązanie.
trevore,
1

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.

trevore
źródło
Nie rozumiem tego s jest wejściem. Nie możesz założyć, że s jest posortowane. Twój algorytm musi działać dla wszystkich możliwych wartości s.
DW
Tak, ale w każdym optymalnym rozwiązaniu elementy s zawsze będą posortowane rosnąco w nowej tablicy. Zwróć uwagę na krok „Sortuj s”. Zobacz powyższy przykład. Jak dotąd udowodniłem, że: dla a, b in s, a <b, jeśli a jest optymalnie umieszczone wu, to optymalne miejsce dla b znajduje się na prawo od a.
trevore,