Algorithm to sort pairs of numbers

Question

I already asked this question on stackoverflow, but maybe it is better suited for this site.

The problem is:

I have N pairs of unsigned integerers. I need to sort them. The ending vector of pairs should be sorted nondecreasingly by the first number in each pair and nonincreasingly by the second in each pair. Each pair can have the first and second elements swapped at any point. Sometimes there is no solution, so I need to throw an exception then.

Example:

in pairs:
1 5
7 1
3 8
5 6

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

^^ Without swapping pairs it is impossible to build the solution. So we swap pairs (7, 1), (3, 8) and (5, 6) and build the result. or

in pairs:
1 5
6 9

out:
not possible

Thanks

edit:

Tom Sirgedas on SO proposed the best solution. It is really easy to implement and works in O(log(n) * n). Thank you all for the answers and interest. I really enjoyed mjqxxxx analysis.

Answer 1

Say that two pairs $p_1=(a_1,b_1)$ and $p_2=(a_2,b_2)$ are no-swap compatible if they can be placed in either order in the sorted list without swapping either one. This is true if either $(a_1 \le a_2 \wedge b_1 \ge b_2)$ or $(a_2 \le a_1 \wedge b_2 \ge b_1)$. Note that $p_1$ and $p_2$ are no-swap compatible if and only if they are two-swap compatible (since the partial order defined satisfies $p_1 \preceq p_2 \equiv p_2^{*} \preceq p_1^{*}$, where $*$ denotes the swap operation). Finally, $p_1$ and $p_2$ are one-swap compatible if they can be placed in either order in the sorted list with exactly one of them swapped. This is true if $p_1^{*}$ and $p_2$ are no-swap compatible. In the remaining cases, $p_1$ and $p_2$ are simply incompatible: they cannot satisfy the order condition regardless of their swap state.

The problem can now be solved as follows. Test every pair of pairs. If any pair is incompatible, there is no solution, and we can throw an exception. Otherwise, consider the graph with nodes corresponding to the original pairs, and edges between those pairs of nodes that are not one-swap compatible. Each such pair of nodes must have the same swap state in any properly sorted list, and therefore all nodes in each connected component of the graph must have the same swap state. We need to determine if these component-wide swap states can be consistently assigned. Test all pairs of nodes within each connected component. If any pair is not no-swap compatible, there is no solution, and we can throw an exception. Now test all pairs of connected components (i.e., for components $C_1$ and $C_2$, test all pairs of nodes $p_1 \in C_1$ and $p_2 \in C_2$). We know that each pair of components is at least one-swap compatible, but some pairs may also be no-swap compatible (because each pair of nodes not connected by an edge is at least one-swap compatible, and may also be no-swap compatible). Consider a reduced graph with nodes corresponding to the connected components, and an edge between two nodes if the corresponding components are not no-swap compatible. There is a solution to the original problem if and only if this graph is $2$-colorable. If there is no $2$-coloring, there is no solution, and we can throw an exception. If there is one, then swap all nodes in all components of a single color. We are now guaranteed that any two nodes are no-swap compatible, and so we can properly sort the list of pairs using the defined partial order.

Each step in the algorithm, and hence the entire algorithm, can be performed in $O(N^2)$ time.

---

UPDATE: A much more elegant construction is the following. If a pair of pairs is not no-swap compatible, connect the corresponding nodes with an edge (forcing them to be different colors in any 2-coloring). If a pair of pairs is not one-swap compatible, connect the corresponding nodes with a chain of length 2 (forcing them to be the same color in any 2-coloring). There is a solution if and only if the resulting graph is 2-colorable. To construct a solution from a blue-red coloring of the graph, swap just those pairs whose corresponding nodes are blue, then sort the resulting list.

Answer 2

Let X(a, b) denote the binary variable indicating whether pair (a, b) should be swapped. Consider any couple of distinct pairs (a, b) and (c, d) and write a binary constraint on the variables X(a, b) and X(c, d) that is satisfied if and only if the two pairs are in the correct order after performing the swaps indicated by X(a, b) and X(c, d), respectively. The conjunction of all such binary constraints is a 2-SAT formula in n variables and O(n^2) clauses which is satisfiable if and only if the original problem has a solution. This can be checked in time O(n^2).

---

As for the original solution, just note that all constraints are of the form X(a, b) = X(c, d) or X(a, b) != X(c, d) (or else X(a, b) = constant), so a simple "merge and check for bipartiteness" algorithm works:

Start with each X being the representative for the set containing only itself; then for every pair (X, Y) such that X = Y is a constraint, merge the components to which X and Y belong; and finally check that the contracted graph, where each component is one vertex and some edge joins the components containing X and Y if the relationship X != Y must hold, is bipartite.