Алгоритм сортировки пар чисел

Я уже задавал этот вопрос на stackoverflow , но, возможно, он лучше подходит для этого сайта.

Проблема в:

У меня N пар целых чисел без знака. Мне нужно их отсортировать. Конечный вектор пар должен сортироваться неуклонно по первому числу в каждой паре и неуклонно по второму в каждой паре. Каждая пара может поменять местами первый и второй элементы в любой точке. Иногда решения не существует, поэтому мне нужно создать исключение.

Пример:

in pairs:
1 5
7 1
3 8
5 6

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

^^ Без обмена парами невозможно построить решение. Таким образом, мы меняем пары (7, 1), (3, 8) и (5, 6) и строим результат. или

in pairs:
1 5
6 9

out:
not possible

Благодарность

редактировать:

Том Сиргедас на SO предложил лучшее решение . Это действительно легко реализовать и работает в O (log (n) * n). Спасибо всем за ответы и интерес. Мне очень понравился анализ mjqxxxx.

Скажем , что две пары и р 2 = ( 2 , б 2 ) не нет замены совместимы , если они могут быть размещены в любом порядке в отсортированном списке , не меняя ни один. Это верно, если либо ( a 1 ≤ a 2 ∧ b 1 ≥ b 2 ), либо ( a 2 ≤ a 1 ∧ b 2 ≥ $p_1=(a_1,b_1)$$p_2=(a_2,b_2)$$(a_1 \le a_2 \wedge b_1 \ge b_2)$ . Заметимчто р 1 и р 2 p ∗ 1 и$(a_2 \le a_1 \wedge b_2 \ge b_1)$$p_1$$p_2$совместимы без обмена, если и только если они совместимы с двумя обменами (поскольку определенный частичный порядок удовлетворяет условию , где ∗ обозначает операцию обмена). Наконец, р 1 и р 2 являются один замены совместимы , если они могут быть размещены в любом порядке в отсортированном списке ровно один из них поменялись местами. Это верно, если$p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$$*$$p_1$$p_2$$p_1^{*}$ не совместимы без обмена. В остальных случаях p 1 и p 2 просто несовместимы: они не могут удовлетворять условию заказа независимо от их состояния обмена.$p_2$$p_1$$p_2$

Теперь проблема может быть решена следующим образом. Проверьте каждую пару пар. Если какая-либо пара несовместима, решения не существует, и мы можем выбросить исключение. В противном случае рассмотрим граф с узлами, соответствующими исходным парам, и ребрами между теми парами узлов, которые не совместимы с одним свопом. Каждая такая пара узлов должна иметь одинаковое состояние обмена в любом правильно отсортированном списке, и поэтому все узлы в каждом связанном компоненте графа должны иметь одинаковое состояние обмена. Нам необходимо определить, можно ли последовательно назначать эти состояния перестановки компонентов. Проверьте все пары узлов в каждом подключенном компоненте. Если какая-либо пара не совместима без подкачки, решения не существует, и мы можем выбросить исключение. Теперь проверьте все пары подключенных компонентов (т. Е. Для компонентов $C_1$и , проверить все пары узлов p 1 ∈ C 1 и p 2 ∈ C $C_2$$p_1 \in C_1$$p_2 \in C_2$ ). Мы знаем, что каждая пара компонентов совместима по крайней мере с одним обменом, но некоторые пары могут также быть совместимыми без замены (поскольку каждая пара узлов, не соединенных ребром, совместима по крайней мере с одним обменом, а также может быть совместимый своп). Рассмотрим сокращенный граф с узлами, соответствующими подключенным компонентам, и ребром между двумя узлами, если соответствующие компоненты не совместимы без обмена. Решение исходной задачи существует тогда и только тогда, когда этот граф -цветен. Если нет $2$$2$-краски, решения нет, и мы можем выбросить исключение. Если есть один, то поменяйте местами все узлы во всех компонентах одного цвета. Теперь мы гарантируем, что любые два узла совместимы без обмена, и поэтому мы можем правильно отсортировать список пар, используя определенный частичный порядок.

Каждый шаг в алгоритме и, следовательно, весь алгоритм может быть выполнен за времени.$O(N^2)$

ОБНОВЛЕНИЕ: намного более изящная конструкция следующая. Если пара пар не совместима без обмена, соедините соответствующие узлы с ребром (заставляя их иметь разные цвета в любой 2-цветовой раскраске). Если пара пар не совместима с одним свопом, соедините соответствующие узлы цепочкой длиной 2 (чтобы они были одного цвета в любой 2-цветовой раскраске). Решение существует тогда и только тогда, когда полученный граф является 2-раскрашиваемым. Чтобы построить решение из сине-красной раскраски графика, поменяйте местами только те пары, чьи соответствующие узлы синего цвета, а затем отсортируйте результирующий список.

Пусть X (a, b) обозначает двоичную переменную, указывающую, следует ли поменять местами пару (a, b). Рассмотрим любую пару различных пар (a, b) и (c, d) и запишите двоичное ограничение на переменные X (a, b) и X (c, d), которое выполняется тогда и только тогда, когда две пары находятся в правильный порядок после выполнения перестановок, обозначенных X (a, b) и X (c, d) соответственно. Соединение всех таких бинарных ограничений является формулой 2-SAT из n переменных и O (n ^ 2) выражений, которая выполнима тогда и только тогда, когда исходная задача имеет решение. Это можно проверить за время O (n ^ 2).

Что касается исходного решения, просто отметьте, что все ограничения имеют вид X (a, b) = X (c, d) или X (a, b)! = X (c, d) (или же X (a, б) = константа), поэтому работает простой алгоритм «слияния и проверки на двойственность»:

Начните с каждого X, являющегося представителем множества, содержащего только себя; затем для каждой пары (X, Y), для которой X = Y является ограничением, объединить компоненты, к которым относятся X и Y; и, наконец, проверьте, что сжатый граф, где каждый компонент представляет собой одну вершину, а некоторое ребро соединяет компоненты, содержащие X и Y, если должно соблюдаться соотношение X! = Y, является двудольным.