Algorytm sortowania par liczb

Zadałem już to pytanie przy przepełnieniu stosu , ale może lepiej pasuje do tej witryny.

Problemem jest:

Mam N par liczb całkowitych bez znaku. Muszę je posortować. Wektor końcowy par należy posortować nie malejąco według pierwszej liczby w każdej parze i nieskończenie według drugiej liczby w każdej parze. Każda para może zamieniać pierwszy i drugi element w dowolnym momencie. Czasami nie ma rozwiązania, więc muszę rzucić wyjątek.

Przykład:

in pairs:
1 5
7 1
3 8
5 6

out pairs:
1 7     <-- swapped
1 5     
6 5     <-- swapped
8 3     <-- swapped

^^ Bez zamiany par niemożliwe jest zbudowanie rozwiązania. Zamieniamy więc pary (7, 1), (3, 8) i (5, 6) i budujemy wynik. lub

in pairs:
1 5
6 9

out:
not possible

Dzięki

edytować:

Tom Sirgedas w SO zaproponował najlepsze rozwiązanie . Jest naprawdę łatwy do wdrożenia i działa w O (log (n) * n). Dziękujemy wszystkim za odpowiedzi i zainteresowanie. Naprawdę podobała mi się analiza mjqxxxx.

$p_1=(a_1,b_1)$$p_2=(a_2,b_2)$$(a_1 \le a_2 \wedge b_1 \ge b_2)$$(a_2 \le a_1 \wedge b_2 \ge b_1)$$p_1$$p_2$$p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$$*$$p_1$$p_2$$p_1^{*}$$p_2$$p_1$$p_2$

$C_1$$C_2$$p_1 \in C_1$$p_2 \in C_2$$2$$2$-kolorowanie, nie ma rozwiązania i możemy zgłosić wyjątek. Jeśli istnieje, zamień wszystkie węzły we wszystkich komponentach jednego koloru. Mamy teraz gwarancję, że dowolne dwa węzły są kompatybilne bez wymiany, dzięki czemu możemy poprawnie sortować listę par przy użyciu zdefiniowanej częściowej kolejności.

$O(N^2)$

AKTUALIZACJA: O wiele bardziej elegancka konstrukcja jest następująca. Jeśli para par nie jest kompatybilna bez wymiany, połącz odpowiednie węzły za pomocą krawędzi (zmuszając je do różnych kolorów w dowolnym kolorze 2). Jeśli para par nie jest kompatybilna z jedną wymianą, połącz odpowiednie węzły łańcuchem o długości 2 (zmuszając je do tego samego koloru w dowolnym kolorze 2). Istnieje rozwiązanie wtedy i tylko wtedy, gdy wynikowy wykres jest dwukolorowy. Aby skonstruować rozwiązanie z niebiesko-czerwonego zabarwienia wykresu, zamień tylko te pary, których odpowiadające węzły są niebieskie, a następnie posortuj wynikową listę.

Niech X (a, b) oznacza zmienną binarną wskazującą, czy para (a, b) powinna zostać zamieniona. Rozważ dowolną parę odrębnych par (a, b) i (c, d) i napisz binarne ograniczenie na zmienne X (a, b) i X (c, d), które jest spełnione tylko wtedy, gdy obie pary są w prawidłową kolejność po wykonaniu zamiany wskazanej odpowiednio przez X (a, b) i X (c, d). Połączeniem wszystkich takich ograniczeń binarnych jest formuła 2-SAT w n zmiennych i klauzulach O (n ^ 2), która jest zadowalająca tylko wtedy, gdy pierwotny problem ma rozwiązanie. Można to sprawdzić w czasie O (n ^ 2).

Jeśli chodzi o oryginalne rozwiązanie, pamiętaj, że wszystkie ograniczenia mają postać X (a, b) = X (c, d) lub X (a, b)! = X (c, d) (lub X (a, b) = stała), więc działa prosty algorytm „scal i sprawdź dwustronność”:

Zacznij od tego, że każdy X jest reprezentatywny dla zestawu zawierającego tylko siebie; następnie dla każdej pary (X, Y) tak, że X = Y jest ograniczeniem, połącz składniki, do których należą X i Y; i na koniec sprawdź, czy wykres skurczony, w którym każdy element jest jednym wierzchołkiem, a jakaś krawędź łączy elementy zawierające X i Y, jeśli relacja X! = Y musi być zachowana, jest dwustronny.