Algoritmo para ordenar pares de números

Ya hice esta pregunta en stackoverflow , pero tal vez sea más adecuada para este sitio.

El problema es:

Tengo N pares de enteros sin signo. Necesito ordenarlos. El vector final de los pares debe clasificarse de manera no decreciente por el primer número de cada par y no cada vez más por el segundo de cada par. Cada par puede tener el primer y el segundo elemento intercambiados en cualquier punto. A veces no hay solución, entonces necesito lanzar una excepción.

Ejemplo:

in pairs:
1 5
7 1
3 8
5 6

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

^^ Sin intercambio de pares es imposible construir la solución. Entonces intercambiamos pares (7, 1), (3, 8) y (5, 6) y construimos el resultado. o

in pairs:
1 5
6 9

out:
not possible

Gracias

editar:

Tom Sirgedas en SO propuso la mejor solución . Es realmente fácil de implementar y funciona en O (log (n) * n). Gracias a todos por las respuestas e interés. Realmente disfruté el análisis mjqxxxx.

Digamos que dos pares y p 2 = ( a 2 , b 2 ) no son compatibles con el intercambio si se pueden colocar en cualquier orden en la lista ordenada sin intercambiar ninguno. Esto es cierto si ( a 1 ≤ a 2 ∧ b 1 ≥ b 2 ) o ( 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)$y$(a_2 \le a_1 \wedge b_2 \ge b_1)$. Tenga en cuenta que y p 2 son compatibles sin intercambio si y solo si son compatibles con dos intercambios (ya que el orden parcial definido satisface p 1 ⪯ p 2 ≡ p ∗ 2 ⪯ p ∗ 1 , donde ∗ indica la operación de intercambio) . Finalmente, p 1 y p 2 son compatibles con un intercambio si se pueden colocar en cualquier orden en la lista ordenada con exactamente uno de ellos intercambiado. Esto es cierto si p ∗$p_1$$p_2$$p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$$*$$p_1$$p_2$$p_1^{*}$ son compatibles sin intercambio. En los casos restantes, p 1 y p 2 son simplemente incompatibles: no pueden satisfacer la condición del pedido independientemente de su estado de intercambio.$p_2$$p_1$$p_2$

El problema ahora se puede resolver de la siguiente manera. Prueba cada par de pares. Si algún par es incompatible, no hay solución y podemos lanzar una excepción. De lo contrario, considere el gráfico con nodos correspondientes a los pares originales, y los bordes entre esos pares de nodos que no son compatibles con un intercambio. Cada uno de estos pares de nodos debe tener el mismo estado de intercambio en cualquier lista ordenada adecuadamente y, por lo tanto, todos los nodos en cada componente conectado del gráfico deben tener el mismo estado de intercambio. Necesitamos determinar si estos estados de intercambio de todo el componente pueden asignarse de manera consistente. Pruebe todos los pares de nodos dentro de cada componente conectado. Si algún par no es compatible sin intercambio, no hay solución y podemos lanzar una excepción. Ahora pruebe todos los pares de componentes conectados (es decir, para los componentes $C_1$ y , pruebe todos los pares de nodos p 1 ∈ C 1 y p 2 ∈ C 2 ). Sabemos que cada par de componentes es al menos compatible con un intercambio, pero algunos pares también pueden no ser compatibles con el intercambio (porque cada par de nodos no conectados por un borde es al menos compatible con un intercambio, y también pueden no ser compatibles) compatible con intercambio). Considere un gráfico reducido con nodos correspondientes a los componentes conectados, y un borde entre dos nodos si los componentes correspondientesnosoncompatibles sin intercambio. Hay una solución al problema original si y solo si este gráfico es 2 -colorable. Si no hay$C_2$$p_1 \in C_1$$p_2 \in C_2$$2$$2$-color, no hay solución, y podemos lanzar una excepción. Si hay uno, intercambie todos los nodos en todos los componentes de un solo color. Ahora tenemos la garantía de que cualquiera de los dos nodos son compatibles sin intercambio, por lo que podemos ordenar correctamente la lista de pares utilizando el orden parcial definido.

Cada paso en el algoritmo, y por lo tanto el algoritmo completo, se puede realizar en tiempo .$O(N^2)$

ACTUALIZACIÓN: Una construcción mucho más elegante es la siguiente. Si un par de pares no es compatible sin intercambio, conecte los nodos correspondientes con un borde (forzándolos a tener diferentes colores en cualquier color 2). Si un par de pares no es compatible con un intercambio, conecte los nodos correspondientes con una cadena de longitud 2 (forzándolos a ser del mismo color en cualquier color 2). Hay una solución si y solo si el gráfico resultante es de 2 colores. Para construir una solución a partir de una coloración azul-roja del gráfico, intercambie solo aquellos pares cuyos nodos correspondientes sean azules, luego ordene la lista resultante.

Deje X (a, b) denotar la variable binaria que indica si el par (a, b) debe intercambiarse. Considere cualquier par de pares distintos (a, b) y (c, d) y escriba una restricción binaria sobre las variables X (a, b) y X (c, d) que se satisfaga si y solo si los dos pares están en el orden correcto después de realizar los intercambios indicados por X (a, b) y X (c, d), respectivamente. La conjunción de todas estas restricciones binarias es una fórmula 2-SAT en n variables y cláusulas O (n ^ 2) que es satisfactoria si y solo si el problema original tiene una solución. Esto se puede verificar en el tiempo O (n ^ 2).

En cuanto a la solución original, solo tenga en cuenta que todas las restricciones son de la forma X (a, b) = X (c, d) o X (a, b)! = X (c, d) (o bien X (a, b) = constante), por lo que funciona un algoritmo simple "fusionar y verificar la bipartita":

Comience con cada X como representante del conjunto que solo se contiene a sí mismo; luego, para cada par (X, Y) de modo que X = Y sea una restricción, combine los componentes a los que pertenecen X e Y; y finalmente verifique que el gráfico contraído, donde cada componente es un vértice y algún borde se une a los componentes que contienen X e Y, si la relación X! = Y debe mantenerse, es bipartito.